01 Matrix
MedPrompt
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two cells sharing a common edge is 1.
Example 1:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]Example 2:
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j]is either0or1.- There is at least one
0inmat.
Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward but highly inefficient approach. The idea is to iterate through every cell of the matrix. If a cell contains a 1, we then perform another complete scan of the entire matrix to find the minimum distance to a cell containing a 0.
Algorithm
- Create a result matrix
distof the same size as the inputmat. - Iterate through each cell
(r, c)of the input matrix. - If
mat[r][c]is0, the distance is0, so setdist[r][c] = 0. - If
mat[r][c]is1, we must find the nearest0. Initialize a variablemin_distto a very large value. - Start a second, nested traversal over all cells
(i, j)of the matrix. - If
mat[i][j]is0, calculate the Manhattan distance|r - i| + |c - j|and updatemin_distwith the minimum value found so far. - After checking all cells,
dist[r][c]is set to the finalmin_dist. - Return the
distmatrix.
Walkthrough
We create a new result matrix, dist, of the same dimensions as the input mat. We traverse each cell (r, c) of the input matrix. If mat[r][c] is 0, the distance is 0, so we set dist[r][c] = 0. If mat[r][c] is 1, we must find the nearest 0. We initialize a variable min_dist to a very large value. Then, we start a second, nested traversal over all cells (i, j) of the matrix. If we find a cell mat[i][j] that is 0, we calculate the Manhattan distance |r - i| + |c - j| and update min_dist with the minimum value found so far. After checking all cells, dist[r][c] is set to the final min_dist. This process is repeated for every cell containing a 1.
class Solution { public int[][] updateMatrix(int[][] mat) { int m = mat.length; int n = mat[0].length; int[][] dist = new int[m][n]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (mat[r][c] == 0) { dist[r][c] = 0; } else { int min_dist = Integer.MAX_VALUE; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (mat[i][j] == 0) { min_dist = Math.min(min_dist, Math.abs(r - i) + Math.abs(c - j)); } } } dist[r][c] = min_dist; } } } return dist; }}Complexity
Time
O((m * n)^2) - For each of the `m*n` cells, we might iterate through all `m*n` cells again in the worst case.
Space
O(m * n) - To store the result matrix. If modifying the input matrix were allowed, it would be O(1) extra space.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely slow due to its nested loops.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Solutions
Solution
class Solution {public int[][] updateMatrix(int[][] mat) { int m = mat.length, n = mat[0].length; int[][] ans = new int[m][n]; for (int[] row : ans) { Arrays.fill(row, -1); } Deque<int[]> q = new ArrayDeque<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (mat[i][j] == 0) { q.offer(new int[]{i, j}); ans[i][j] = 0; } } } int[] dirs = {-1, 0, 1, 0, -1}; while (!q.isEmpty()) { int[] p = q.poll(); int i = p[0], j = p[1]; for (int k = 0; k < 4; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1) { ans[x][y] = ans[i][j] + 1; q.offer(new int[]{x, y}); } } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.