01 Matrix
Statement
Given an m × n binary matrix matrix, find the distance from each cell to the nearest 0. The distance between two adjacent cells is 1. Cells to the left, right, above, and below the current cell are adjacent.
Constraints
- 1 ≤
matrix.length()≤ 50 - 1 ≤
matrix[i].length()≤ 50 matrix[i][j] ∈ {0, 1}- There’s at least one 0 in
matrix
Solution
"""
production algorithm
"""
class Solution:
def distance(self, matrix):
"""
time complexity O(mn)
space complexity O(1)
"""
m, n = len(matrix), len(matrix[0])
result = [[float("inf") for _ in range(m)] for _ in range(n)]
# forward
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
result[i][j] = 0
else:
up = 1 + result[i - 1][j] if 0 <= i - 1 else float("inf")
left = 1 + result[i][j - 1] if 0 <= j - 1 else float("inf")
result[i][j] = min(result[i][j], up, left)
# backward
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if matrix[i][j] == 0:
result[i][j] = 0
else:
down = 1 + result[i + 1][j] if i + 1 < m else float("inf")
right = 1 + result[i][j + 1] if j + 1 < n else float("inf")
result[i][j] = min(result[i][j], down, right)
return result"""
unit tests
"""
from unittest import TestCase
from algorithms.dynamic_programming.matrix_01.solution import Solution
class SolutionTestCase(TestCase):
def test_distance(self):
# Given
matrix = [[1, 1, 1, 0, 1, 1],
[1, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[1, 0, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 1]]
solution = Solution()
# When
actual = solution.distance(matrix)
# Then
expected = [[3, 2, 1, 0, 1, 2],
[2, 1, 0, 1, 1, 2],
[2, 1, 1, 1, 0, 1],
[1, 0, 1, 2, 1, 1],
[1, 1, 2, 2, 1, 0],
[0, 1, 2, 3, 2, 1]]
self.assertEqual(actual, expected)Strategy
Dynamic Programming.
Explanation
The result matrix is the same size as the input matrix, and initialized with infinity in all cells. Two iterations occur to find the distance to the nearest 0 for all cells. The first iteration steps forward and checks the left and above adjacent cells for their distance to the nearest 0. Only the left and above cells are checked because these cells are behind the current cell in a forward iteration. Then a second iteration occurs.
The second iteration steps backwards from the end of the matrix to find the distance to the nearest 0 for all cells. However, in the second iteration only the right and below cells are checked because these cells are behind the current cell in a backwards iteration. After the second iteration completes, the distance to the nearest 0 for all cells in all directions has been found.
Notice, that the problem has optimal substructure, i.e. the optimal solution for the current cell of some iteration can be found from the optimal solution of a cell behind it. Also notice, that the problem has overlapping subproblems, i.e. the optimal solution of a cell behind the current cell of some iteration can be reused to find the optimal solution of the current cell and other cells further ahead in iteration. Since the problem has optimal substructure and overlapping subproblems, then dynamic programming can be used to solve the problem.
Time Complexity
The matrix is iterated twice. Therefore, the time complexity of the algorithm is O(mn).
Space Complexity
The auxiliary space complexity of the algorithm is O(1).
