# 542. 01 Matrix
Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.
Example 1:
Input:
0 0 0
0 1 0
0 0 0
Output:
0 0 0
0 1 0
0 0 0
Example 2:
Input:
0 0 0
0 1 0
1 1 1
Output:
0 0 0
0 1 0
1 2 1
Note:
The number of elements of the given matrix will not exceed 10,000.
There are at least one 0 in the given matrix.
The cells are adjacent in only four directions: up, down, left and right.
# Solution
Approach 1: BFS -- starting from cells with value == 0
(level 1), find the neighbors as the next level. Time: O(N)
where N is number of cells in matrix. Space: O(N)
for the queue storing up to N items.
Approach 2: to find the nearest 0 it need to consider a path from all 4 directions. To do this we can take 2 sweeps, where the 1st sweep takes care of down and right, and the 2nd takes care of left and bottom. Time and space: O(N)
.
# Code (Python)
Approach 1:
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
result = [[float('inf') for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
queue = deque()
# add first level (all cells with value == 0)
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == 0:
result[row][col] = 0
queue.append((row, col))
neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue:
row, col = queue.popleft()
# all neighbors are potential children for the next level
for delta in neighbors:
new_row, new_col = row + delta[0], col + delta[1]
if not (0 <= new_row < len(matrix) and 0 <= new_col < len(matrix[0])):
continue
# only add to queue if value's updated because otherwise it's already added or been visited
if result[new_row][new_col] > result[row][col] + 1:
result[new_row][new_col] = result[row][col] + 1
queue.append((new_row, new_col))
return result
Approach 2:
def updateMatrix(self, matrix):
result = [[float('inf') for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == 0:
result[row][col] = 0
else:
# update values: we've already updated result[row-1][col] and result[row][col-1] before
if row >= 1:
result[row][col] = min(result[row][col], result[row-1][col] + 1)
if col >= 1:
result[row][col] = min(result[row][col], result[row][col-1] + 1)
for row in range(len(matrix) - 1, -1, -1):
for col in range(len(matrix[0]) - 1, -1, -1):
if row < len(matrix) - 1:
result[row][col] = min(result[row][col], result[row+1][col] + 1)
if col < len(matrix[0]) - 1:
result[row][col] = min(result[row][col], result[row][col+1] + 1)
return result
# Code (C++)
Approach 1:
Approach 2: