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