Problem statement

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

Solution

The idea is that answer for each cell we need to find closest distance to water. So, we start multi-source bfs from all water cells. Also in the start invert all elements of matrix.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def highestPeak(self, grid):
        grid = [[1-x for x in row] for row in grid]
        m, n = len(grid), len(grid[0])
        q = deque([(0, i, j) for i in range(m) for j in range(n) if grid[i][j] == 0])    
        ans = 0

        V = set()
        while q:
            dist, i, j = q.popleft()
            for x, y in (1, 0), (-1, 0), (0, 1), (0, -1):
                xi, yj = x+i, y+j
                if 0 <= xi < m and 0 <= yj < n and grid[xi][yj] == 1 and (xi, yj) not in V:
                    V.add((xi, yj))
                    q += [(dist + 1, xi, yj)]
                    grid[xi][yj] = dist + 1
        
        return grid