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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Matrices

Dynamic programming

Data structures

Graph traversal

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)
				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))