LeetCode #542 01 Matrix

Medium

Problem

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:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

Solution — BFS

It’s trivial that we can do BFS to update path to zero of each element. However, if one performs BFS start from each non-zero element, the time complexity will be O((mn)²), where m and n denote to counts of rows and columns correspondingly. It’s too slow and we can’t tolerant it.

On the other hand, if we can perform BFS start from all 0s and update its neighbors, all elements will only be reached once. It’s will be better than previous idea.

Complexity

As we said, each element will be only update once due to checking on matrix[row][col] > matrix[i][j] + 1, which means only the closest zero can update the element. Thus, time complexity will be only O(mn), where m and n denote to counts of rows and columns in this matrix.

For space complexity, the queue will use O(mn) extra space.

Solution — Dynamic Programming

If we take a look more carefully, we will find that after scanning from top-left, the path of top and left elements of all elements are determined by their top and left elements. Hence we have a formula:

matrix[i][j] = min(matrix[i][j], matrix[i-1][j], matrix[i][j-1])

And because we have four directions, we should also take care about bottom and left:

matrix[i][j] = min(matrix[i][j], matrix[i+1][j], matrix[i][j+1])

Therefore, four directions are all considered after these two scans.

Complexity

Because of two scans with different directions, it takes O(mn + mn) = O(mn) time if m and n denote to counts of rows and columns in this matrix.

Because it performs update in place, so its space complexity is only O(1).