# 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: