Today’s problem

https://leetcode.com/problems/map-of-highest-peak/description/

Intuition

Because the maximum absolute value of the height difference between two adjacent grid is 1, and the height of water gird is 0. This means that the answer is just the manhattan distance to the nearest water grid.

Approach

Use a BFS to find the nearest manhattan idstance to a water grid.

Complexity

  • Time complexity: $O(NM)$, N, M are the length and width of the grid.

  • Space complexity: $O(NM)$

Code

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        q = deque()
        ans = [[2005 for _ in range(len(isWater[0]))] for _ in range(len(isWater))]
        for i in range(len(isWater)):
            for j in range(len(isWater[0])):
                if isWater[i][j] == 1:
                    q.append((i,j))
                    ans[i][j] = 0
        
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]

        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= len(isWater) or ny >= len(isWater[0]) or ans[nx][ny] <= ans[x][y] + 1:
                    continue
                ans[nx][ny] = ans[x][y] + 1
                q.append((nx, ny))
        
        return ans