# 01 Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/01-matrix)
Canonical: https://scaleengineer.com/dsa/problems/01-matrix
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Graviton](https://scaleengineer.com/companies/graviton)
---
## Problem
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:**

![](https://assets.glich.co/dsa/01-matrix/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/01-matrix/image1.jpg) 

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

**Constraints:**

* `m == mat.length`
* `n == mat[i].length`
* `1 <= m, n <= 104`
* `1 <= m * n <= 104`
* `mat[i][j]` is either `0` or `1`.
* There is at least one `0` in `mat`.

**Note:** This question is the same as 1765: [https://leetcode.com/problems/map-of-highest-peak/](https://leetcode.com/problems/map-of-highest-peak/description/)

# Approaches
## Brute Force by Scanning for Each Cell
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`.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### Algorithm
*   Create a result matrix `dist` of the same size as the input `mat`.
*   Iterate through each cell `(r, c)` of the input matrix.
*   If `mat[r][c]` is `0`, the distance is `0`, so set `dist[r][c] = 0`.
*   If `mat[r][c]` is `1`, we must find the nearest `0`. Initialize a variable `min_dist` to a very large value.
*   Start a second, nested traversal over all cells `(i, j)` of the matrix.
*   If `mat[i][j]` is `0`, 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`.
*   Return the `dist` matrix.

## Dynamic Programming with Two Passes
A much more efficient approach uses dynamic programming. The distance of a cell to the nearest `0` depends on the distances of its neighbors. We can't solve this with a single pass because of dependencies in all four directions. However, we can solve it with two passes over the matrix: one from top-left to bottom-right, and another from bottom-right to top-left.
**Time:** O(m * n) - We perform two full passes over the matrix. · **Space:** O(m * n) - For the `dist` matrix.
**Pros:** Very efficient with linear time complexity.; Does not require an explicit queue data structure, which can sometimes lead to better cache performance.
**Cons:** The logic can be less intuitive to come up with compared to a standard BFS.
### Explanation
The first pass goes from top-left to bottom-right. It calculates the distance for each cell `(i, j)` based on the distances of the cells above it `(i-1, j)` and to its left `(i, j-1)`. This effectively propagates distances from `0`s that are located to the top-left of the current cell. The second pass goes from bottom-right to top-left. It updates the distance for each cell `(i, j)` based on the distances of the cells below it `(i+1, j)` and to its right `(i, j+1)`. This pass propagates distances from `0`s located to the bottom-right. By combining these two passes, we ensure that for every cell, we have considered the shortest path from a `0` regardless of its relative position.

```java
class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        int maxDist = m + n; // A safe upper bound for any distance

        // First pass: top-left to bottom-right
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = maxDist;
                    if (i > 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    }
                    if (j > 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
        }

        // Second pass: bottom-right to top-left
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i < m - 1) {
                    dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                }
                if (j < n - 1) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                }
            }
        }
        return dist;
    }
}
```
### Algorithm
*   Initialize a `dist` matrix of size `m x n`. For cells with `0` in `mat`, set `dist` to `0`. For cells with `1`, set `dist` to a large value (e.g., `m + n`).
*   **Pass 1 (Top-Left to Bottom-Right):**
    *   For `i` from `0` to `m-1`:
        *   For `j` from `0` to `n-1`:
            *   If `i > 0`, update `dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)`.
            *   If `j > 0`, update `dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)`.
*   **Pass 2 (Bottom-Right to Top-Left):**
    *   For `i` from `m-1` down to `0`:
        *   For `j` from `n-1` down to `0`:
            *   If `i < m-1`, update `dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)`.
            *   If `j < n-1`, update `dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)`.
*   Return `dist`.

## Multi-Source Breadth-First Search (BFS)
This is a classic and highly intuitive approach for shortest path problems on unweighted graphs (like a grid). Instead of searching from each `1` for a `0`, we can reverse the problem: find the shortest path from any `0` to all other cells. This can be modeled as a multi-source Breadth-First Search (BFS), where all `0`s are the initial sources.
**Time:** O(m * n) - Each cell is enqueued and dequeued exactly once. · **Space:** O(m * n) - In the worst case, the queue can hold up to `m*n` cells (e.g., a checkerboard pattern). The `dist` matrix also takes `O(m*n)` space.
**Pros:** Very efficient with linear time complexity.; A standard, intuitive pattern for shortest path problems on grids.; Easily adaptable to similar problems.
**Cons:** Requires an explicit queue, which might have slightly more overhead than the DP approach's simple array traversals.
### Explanation
We start by identifying all the 'source' cells, which are the cells containing `0`. Their distance to the nearest `0` is `0`. We add all these source cells to a queue. We also initialize a `dist` matrix. We can use the input matrix itself to store distances if modification is allowed, or create a new one. Cells with `0` have distance `0`, and cells with `1` can be marked as unvisited (e.g., with a value of -1). Then, we perform a standard BFS. We dequeue a cell, and for each of its unvisited neighbors, we update their distance to be the current cell's distance + 1, and then enqueue them. Because BFS explores layer by layer, the first time we reach a cell, we are guaranteed to have found the shortest path to it from one of the initial `0` sources.

```java
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();

        // Initialize dist matrix and queue with all 0s
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    queue.offer(new int[]{i, j});
                } else {
                    dist[i][j] = -1; // Mark as unvisited
                }
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0];
            int c = cell[1];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                // Check bounds and if the cell is unvisited
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        return dist;
    }
}
```
### Algorithm
*   Get matrix dimensions `m` and `n`.
*   Create a `dist` matrix, initialized with `0` for `0`-cells and a marker for unvisited (e.g., -1) for `1`-cells.
*   Create a queue and add the coordinates of all `0`-cells to it.
*   While the queue is not empty:
    *   Dequeue a cell `(r, c)`.
    *   For each of its four neighbors `(nr, nc)`:
        *   If the neighbor is within bounds and is unvisited (`dist[nr][nc] == -1`):
            *   Set its distance: `dist[nr][nc] = dist[r][c] + 1`.
            *   Enqueue the neighbor `(nr, nc)`.
*   Return the `dist` matrix.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution { public: vector < vector < int >> updateMatrix ( vector < vector < int >>& mat ) { int m = mat . size (), n = mat [ 0 ]. size (); vector < vector < int >> ans ( m , vector < int > ( n , - 1 )); queue < pair < int , int >> q ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( mat [ i ][ j ] == 0 ) { ans [ i ][ j ] = 0 ; q . emplace ( i , j ); } } } vector < int > dirs = { - 1 , 0 , 1 , 0 , - 1 }; while ( ! q . empty ()) { auto p = q . front (); q . pop (); for ( int i = 0 ; i < 4 ; ++ i ) { int x = p . first + dirs [ i ]; int y = p . second + dirs [ i + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && ans [ x ][ y ] == - 1 ) { ans [ x ][ y ] = ans [ p . first ][ p . second ] + 1 ; q . emplace ( x , y ); } } } return ans ; } };
```

### Python

```python
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) ans = [[- 1] * n for _ in range(m)] q = deque() for i, row in enumerate(mat): for j, x in enumerate(row): if x == 0: ans[i][j] = 0 q . append((i, j)) dirs = (- 1, 0, 1, 0, - 1) while q: i, j = q . popleft() for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and ans[x][y] == - 1: ans[x][y] = ans[i][j] + 1 q . append((x, y)) return ans

```