Skip to main content

01 Matrix

Problem Description​

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: image

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

Example 2:

image

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 <= 10^4
  • 1 <= m * n <= 10^4
  • mat[i][j] is either 0 or 1.
  • There is at least one 0 in mat.

Solution for 542. 01 Matrix Problem​

Approach​

  1. Initialization:

    • Create a queue q to perform a Breadth-First Search (BFS).
    • Create a vis matrix to keep track of visited cells.
    • Create a dis matrix to store the distance of each cell from the nearest 0.

  2. Enqueue All Zeros:

    • Iterate through each cell in the matrix.
    • If a cell contains 0, enqueue it with a distance of 0 and mark it as visited in the vis matrix.
    • If a cell contains 1, mark it as not visited in the vis matrix.

  3. Define Directions:

    • Define arrays drow and dcol to represent the four possible directions (up, right, down, left).

  4. BFS Traversal:

    • While the queue is not empty:
      • Dequeue the front element.
      • For each direction:
        • Calculate the new row and column indices.
        • Check if the new indices are within the bounds and the cell is not visited.
        • If valid, mark the cell as visited, enqueue it with the incremented distance, and update the dis matrix.

  5. Return Result:

    • After the BFS completes, the dis matrix contains the required distances.

Implementation​

Live Editor
function Solution(arr) {
var updateMatrix = function(mat) {
    let n = mat.length;
    let m = mat[0].length;

    let q = [];
    let vis = Array.from({ length: n }, () => Array(m).fill(0));
    let dis = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (mat[i][j] === 0) {
                q.push([[i, j], 0]);
                vis[i][j] = 1;
            } else {
                vis[i][j] = 0;
            }
        }
    }
    let drow = [-1, 0, 1, 0];
    let dcol = [0, 1, 0, -1];

    while (q.length) {
        let [pos, steps] = q.shift();
        let [row, col] = pos;
        dis[row][col] = steps;
        for (let i = 0; i < 4; i++) {
            let nrow = row + drow[i];
            let ncol = col + dcol[i];
            if (nrow >= 0 && ncol >= 0 && nrow < n && ncol < m && vis[nrow][ncol] === 0) {
                vis[nrow][ncol] = 1;
                q.push([[nrow, ncol], steps + 1]);
            }
        }
    }
    return dis;
};

  const input = [[0,0,0],[0,1,0],[1,1,1]]
  const output = updateMatrix(input)
  return (
    <div>
      <p>
        <b>Input: </b>
        {JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(n∗m)O(n*m)
  • Space Complexity: O(n∗m) O(n*m)

Code in Different Languages​

Written by @hiteshgahanolia
var updateMatrix = function(mat) {
 let n = mat.length;
 let m = mat[0].length;

 let q = [];
 let vis = Array.from({ length: n }, () => Array(m).fill(0));
 let dis = Array.from({ length: n }, () => Array(m).fill(0));

 for (let i = 0; i < n; i++) {
     for (let j = 0; j < m; j++) {
         if (mat[i][j] === 0) {
             q.push([[i, j], 0]);
             vis[i][j] = 1;
         } else {
             vis[i][j] = 0;
         }
     }
 }
 let drow = [-1, 0, 1, 0];
 let dcol = [0, 1, 0, -1];

 while (q.length) {
     let [pos, steps] = q.shift();
     let [row, col] = pos;
     dis[row][col] = steps;
     for (let i = 0; i < 4; i++) {
         let nrow = row + drow[i];
         let ncol = col + dcol[i];
         if (nrow >= 0 && ncol >= 0 && nrow < n && ncol < m && vis[nrow][ncol] === 0) {
             vis[nrow][ncol] = 1;
             q.push([[nrow, ncol], steps + 1]);
         }
     }
 }
 return dis;
};

References​