Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.
The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.
If no land or water exists in the grid, return -1.
 
Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

 
Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

Difficulty: interview

Starter code:

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        
        from collections import deque
        
        queue = deque()
        for i, row in enumerate(grid):
            for j, cell in enumerate(row):
                if cell == 1:
                    queue.append((i, j, None, None))
        
        dist = {}
        while queue:
            
            i, j, previ, prevj = queue.popleft()
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
                continue
            if (i, j) not in dist:
                dist[(i, j)] = 1 + dist.get((previ, prevj), -1)
                # if previ is None and prevj is None:
                #     dist[(i, j)] = 0
                # else:
                #     dist[(i, j)] = 1 + dist[(previ, prevj)]
                for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    newi, newj = i +di, j + dj
                    queue.append((newi, newj, i, j))
        
        ans = max(list(dist.values()), default=-1)
        return ans if ans != 0 else -1
                
            
            


from queue import PriorityQueue

class Solution:
    def isInRange(self, grid, x, y):
        return (0 <= x and x < len(grid[0])) and (0 <= y and y < len(grid))

    def maxDistance(self, grid: List[List[int]]) -> int:
        q = PriorityQueue()
        visited = dict()
        maxDist = 0
        toVisit = [(-1, 0), (0, 0), (1, 0), (0, 1), (0, -1)]
        
        for x, i in enumerate(grid):
            for y, j in enumerate(i):
                if j is not 0:
                    q.put((0, (x, y)))
                    visited[(x, y)] = True
                    
        if (q.qsize() >= len(grid[0]) * len(grid) or q.qsize() is 0):
            return -1
                    
        while not q.empty():
            item = q.get()
            maxDist = max(maxDist, item[0])
            
            for p in toVisit:
                x = p[0] + item[1][0]
                y = p[1] + item[1][1]
                
                if self.isInRange(grid, x, y) and visited.get((x, y)) is not True:
                    visited[(x, y)] = True
                    q.put((item[0] + 1, (x, y)))
            
        return maxDist

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[math.inf] * n for _ in range(m)]
        land = water = 0

        for i, row in enumerate(grid):
            for j, cell in enumerate(row):
                if cell:
                    dp[i][j] = 0
                    land += 1
                else:
                    water += 1

        if not land or not water:
            return -1

        def process(dp):
            for i in range(m):
                for j in range(n):
                    if i:
                        dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
                    if j:
                        dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)

        process(dp)
        dp = dp[::-1]
        process(dp)
        dp = [row[::-1] for row in dp]
        process(dp)
        dp = dp[::-1]
        process(dp)

        return max(max(row) for row in dp)