LC 1765


Solution to LeetCode 1765 Map of Highest Peak.

LeetCode 1765

Map of Highest Peak (Medium). [link]

Time complexity O(NM). Space complexity O(NM). N is the column length and M is the row length.

class Solution(object):
    def highestPeak(self, isWater):
        """
        :type isWater: List[List[int]]
        :rtype: List[List[int]]
        """

        rows, cols = len(isWater), len(isWater[0])
        res = [[water - 1 for water in row] for row in isWater]  # create a grid in same size
        q = deque((i,j) for i, row in enumerate(isWater) for j, water in enumerate(row) if water) # push waters in queue
        while q:
            i, j = q.popleft()
            for x, y in ((i - 1, j),(i + 1, j),(i, j - 1),(i, j + 1)): # all neighbors + 1
                if 0 <= x < rows and 0 <= y < cols and res[x][y] == -1:
                    res[x][y] = res[i][j] + 1
                    q.append((x,y))
        return res

  TOC