Problem

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Examples

Example 1: $$ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} $$

1
2

Input: mat =[[0,0,0],[0,1,0],[0,0,0]]
Output:[[0,0,0],[0,1,0],[0,0,0]]

Example 2: $$ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix} $$

1
2

Input: mat =[[0,0,0],[0,1,0],[1,1,1]]
Output:[[0,0,0],[0,1,0],[1,2,1]]

Solution

Method 1 - BFS

  • For convenience, let’s refer to cells with a value of 0 as zero-cell, those with a value of 1 as one-cell, and the distance to the nearest 0 as the distance.
  • Initially, the distance for all zero-cells is 0.
  • Using a similar approach to Topological Sort, we first process the zero-cells. We utilize a queue data structure to maintain the processing order, ensuring that cells with smaller distances are processed first. We then expand the unprocessed neighbors of the current cell and enqueue them.
  • This approach allows us to determine the minimum distance for all cells in the matrix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

public int[][] updateMatrix(int[][] matrix) {
	  int m = matrix.length;
	if (m == 0) {
		return matrix;
	}
	int n = matrix[0].length;

	int[][] result = new int[m][n];
	Queue<int[]> queue = new LinkedList<>(); // cells which has already been optimized
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (matrix[i][j] == 0) {
				queue.add(new int[]{i, j});
			} else {
				result[i][j] = Integer.MAX_VALUE;
			}
		}
	}

	int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	while (!queue.isEmpty()) {
		int[] pair = queue.poll();
		int r = pair[0];
		int c = pair[1];
		for (int[] dir : dirs) {
			int newR = pair[0] + dir[0];
			int newC = pair[1] + dir[1];
			if (newR >= 0 && newR < m && newC >= 0 && newC < n) {
				if (result[newR][newC] > result[r][c] + 1) { // check if neighbor is optimized or not
					result[newR][newC] = result[r][c] + 1;
					queue.add(new int[]{newR, newC});
				}
			}
		}
	}
	return result;
}