medium 01 Matrix

Problem Statement

Given an m x n matrix mat containing only 0 and 1, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells of mat is 1.

Examples

Example 1:

• Input: mat =

[[1,0,1,1],
 [1,1,1,1],
 [1,1,1,0]]

• Expected Output:

[[1,0,1,2],
 [2,1,2,1],
 [3,2,1,0]]

• Justification: Each cell updates to the minimum distance to a zero, with the edges being closest and moving inward, the distance increases.

Example 2:

• Input: mat =

[[0,1,1],
 [1,1,0],
 [1,0,1]]

• Expected Output:

[[0,1,1],
 [1,1,0],
 [1,0,1]]

• Justification: Starting with the zeros, we update their neighbors. The zeros remain zeros since they are already at the nearest zero. The ones directly adjacent to a zero become ones, demonstrating their proximity.

Example 3:

• Input: mat =

[[1,1,0],
 [0,1,1],
 [1,1,1]]

• Expected Output:

[[1,1,0],
 [0,1,1],
 [1,2,2]]

• Justification: Output matrix represents the shortest path to a zero for each cell.

Constraints:

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

Solution

To solve this problem, we start by identifying all the cells containing 0s and marking them as starting points. From these points, we perform a breadth-first search (BFS) to explore all their neighboring cells. This approach ensures that each cell is updated with the shortest distance to the nearest zero, considering only vertical and horizontal movements. Using BFS is effective because it naturally explores all possible paths from each zero, updating distances in a way that guarantees the shortest path is found first before moving on to explore longer paths. This strategy is efficient and ensures that every cell is assigned the correct minimum distance.

The choice of BFS for this solution is crucial because it allows us to layer the exploration of the matrix, ensuring that each cell's distance is updated relative to its proximity to the nearest zero. As we iterate through the matrix, we maintain a queue to manage the cells being explored, updating their distance based on their position relative to the nearest zero. This method is not only systematic but also ensures that all possible paths are considered, providing an optimal solution to the problem.

Step-by-Step Algorithm

1. Initialization:

   • Determine the dimensions of the input matrix, m (number of rows) and n (number of columns).
   • Create a queue to store the positions (row and column indices) of all the 0s in the matrix.
   • Iterate over the matrix. For each element:
     • If it's a 0, add its position to the queue.
     • If it's a 1, change its value to Integer.MAX_VALUE (in Java) or an equivalent large number to indicate it's not yet visited or updated.

2. Define Directions:

   • Create an array or list of directions to move from any cell (up, down, left, right).

3. Process Queue:

   • While the queue is not empty, perform the following:
     • Remove an element (position) from the queue.
     • Iterate over the defined directions, and for each direction, calculate the new position.
     • If the new position is within bounds and its value is greater than the current position's value plus 1 (indicating a shorter path to a 0 has been found):
       • Update the new position's value to be the current position's value plus 1.
       • Add the new position to the queue to later check its neighbors.

4. Return Updated Matrix:

   • After the queue is empty (all positions processed), return the modified matrix as the final result.

Algorithm Walkthrough

Let's consider the Input: mat = [[1,0,1,1], [1,1,1,1], [1,1,1,0]]

Initial Matrix

1 0 1 1
1 1 1 1
1 1 1 0

Step 1: Initialization

• Queue = {(0, 1), (2, 3)} (Coordinates of the 0s)
• Update all 1s to infinity (Integer.MAX_VALUE or a symbolic equivalent for clarity)

Matrix becomes:

∞ 0 ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ 0

Step 2: Processing (Queue: {(0, 1), (2, 3)})

• First iteration (0, 1):
  • Top: Out of bounds
  • Bottom: (1, 1) updated to 1 (from ∞)
  • Left: (0, 0) updated to 1 (from ∞)
  • Right: (0, 2) updated to 1 (from ∞)
• Queue becomes: {(2, 3), (1, 1), (0, 0), (0, 2)}

After first iteration matrix:

1 0 1 ∞
∞ 1 ∞ ∞
∞ ∞ ∞ 0

• Second iteration (2, 3):
  • Top: (1, 3) updated to 1 (from ∞)
  • Bottom: Out of bounds
  • Left: (2, 2) updated to 1 (from ∞)
  • Right: Out of bounds
• Queue becomes: {(1, 1), (0, 0), (0, 2), (1, 3), (2, 2)}

Matrix after second iteration:

1 0 1 ∞
∞ 1 ∞ 1
∞ ∞ 1 0

• Third Iteration (1, 1):

  • Top: (0, 1) already 0, no update.
  • Bottom: (2, 1) updated to 2 (from ∞).
  • Left: (1, 0) updated to 2 (from ∞).
  • Right: (1, 2) updated to 2 (from ∞).

• Updated Queue: {(0, 0), (0, 2), (1, 3), (2, 2), (2, 1), (1, 0), (1, 2)}

Matrix after this step:

1 0 1 ∞
2 1 2 1
∞ 2 1 0

• Fourth Iteration (0, 0):

  • Top: Out of bounds.
  • Bottom: (1, 0) already 2, no update.
  • Left: Out of bounds.
  • Right: (0, 1) already 0, no update.

• No updates made, proceed to the next cell in the queue.

• Fifth Iteration (0, 2):

  • Top: Out of bounds.
  • Bottom: (1, 2) already 2, no update.
  • Left: (0, 1) already 0, no update.
  • Right: (0, 3) updated to 2 (from ∞).

• Updated Queue: {(1, 3), (2, 2), (2, 1), (1, 0), (1, 2), (0, 3)}

Matrix after this step:

1 0 1 2
2 1 2 1
∞ 2 1 0

• Sixth Iteration (1, 3):

  • Mat remains the same.

• Seventh Iteration (2, 2):

  • Mat remains the same.

• Eighth Iteration (2, 1):

  • Top: (1, 1) already 1, no update
  • Bottom: Out of bound
  • Left: (2, 0) updated to 3 (from ∞).
  • Right: (2, 3) already 0, no update

• Updated Queue: {(1, 0), (1, 2), (0, 3), (2, 0)}

Matrix after this step:

1 0 1 2
2 1 2 1
3 2 1 0

Subsequent Iterations

Proceeding with the next elements in the queue, updating neighbors where applicable. Each step involves checking the top, bottom, left, and right neighbors for potential updates, following the same pattern as demonstrated.

Final Iteration Steps

• Process (1, 0), (1, 2), (0, 3), (2, 0): Each of these cells will have its neighbors checked. Updates are made only if the current distance + 1 is less than the neighbor's distance.

• After processing all elements in the queue, the final distances are calculated. Each '∞' symbol gets replaced with the calculated minimum distance to the nearest '0'.

Final Matrix

1 0 1 2
2 1 2 1
3 2 1 0

This matrix represents the completed calculation, with each cell now showing the minimum distance to the nearest 0, adhering strictly to the described approach and order of neighbor visitation.

Code

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution {

  // Method to update the matrix with distances from nearest 0
  public int[][] updateMatrix(int[][] mat) {
    // Dimensions of the matrix
    int m = mat.length, n = mat[0].length;

    // Queue to hold coordinates of cells with 0s
    Queue<int[]> queue = new LinkedList<>();

    // Iterating through the matrix
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // If cell value is 0, add its coordinates to the queue
        if (mat[i][j] == 0) {
          queue.add(new int[] { i, j });
        } else {
          // If cell value is not 0, initialize it to maximum value
          // This is used as a placeholder for distance calculation
          mat[i][j] = Integer.MAX_VALUE;
        }
      }
    }

    // Directions to move in the matrix
    int[][] dirs = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    // Breadth-first search
    while (!queue.isEmpty()) {
      int[] cell = queue.poll(); // Get the current cell
      // Explore neighboring cells
      for (int[] d : dirs) {
        int r = cell[0] + d[0]; // New row coordinate
        int c = cell[1] + d[1]; // New column coordinate
        // Check if the new coordinates are within bounds and if the current distance is greater than calculated distance
        if (
          r < 0 ||
          r >= m ||
          c < 0 ||
          c >= n ||
          mat[r][c] <= mat[cell[0]][cell[1]] + 1
        ) continue;
        // Add the new cell to the queue for further exploration
        queue.add(new int[] { r, c });
        // Update the distance to the new cell
        mat[r][c] = mat[cell[0]][cell[1]] + 1;
      }
    }

    return mat; // Return the updated matrix
  }

  // Main method to test the updateMatrix method
  public static void main(String[] args) {
    Solution solution = new Solution(); // Create an instance of the Solution class
    // Example 1
    int[][] example1 = { { 1, 0, 1, 1 }, { 1, 1, 1, 1 }, { 1, 1, 1, 0 } };
    System.out.println(
      "Example 1 Output: " +
      Arrays.deepToString(solution.updateMatrix(example1))
    );

    // Example 2
    int[][] example2 = { { 0, 1, 1 }, { 1, 1, 0 }, { 1, 0, 1 } };
    System.out.println(
      "Example 2 Output: " +
      Arrays.deepToString(solution.updateMatrix(example2))
    );

    // Example 3
    int[][] example3 = { { 1, 1, 0 }, { 0, 1, 1 }, { 1, 1, 1 } };
    System.out.println(
      "Example 3 Output: " +
      Arrays.deepToString(solution.updateMatrix(example3))
    );
  }
}

Complexity Analysis

Time Complexity

• Best and Worst Case:
  • The algorithm goes through every cell in the matrix at least once. Each cell is inserted into the queue only once, and each removal from the queue is followed by a constant number of operations (checking and potentially updating its neighbors).
  • Since each cell's neighbors are processed at most once, the overall time complexity is linear in terms of the number of cells, , where (m) is the number of rows and (n) is the number of columns in the matrix.

Space Complexity

• Worst Case:
  • In the worst case, the queue might contain all the cells of the matrix before starting to empty, especially if the matrix starts with all 1s and there's only one 0 at the edge or corner. Thus, the space complexity is also due to the queue storage.

🎯 STRICT STANDOUT — 01 Matrix — solution

1. Why / judgment

Init dist inf for 1s, 0 for zeros; queue all zeros. Pop and relax 4-neighbors if shorter. Unweighted => BFS order correct.

2. Big-O derivation (K11)

O(mn). Each cell enqueued once in 0-1 grid BFS variant.
1x1 [0]=>[[0]]; all 1s impossible if constraints guarantee a 0? handle.

3. Pattern + when-NOT (K12)

Name: MULTI-SOURCE BFS

Recognition: nearest zero distances.

When-NOT: Two-pass DP alternative. Dijkstra if weights.

4. Edge hand-run (K13)

manual small grid layer expansion.

5. Interviewer follow-ups (model answers)

Q1. Why not per-cell BFS?
A: That is O((mn)^2).

Q2. Visited discipline?
A: Only update when improve; first BFS hit is shortest.

Q3. DP two-pass idea?
A: Forward relax left/up; backward right/down.

6. Short drills

Drill A: queue seeds.
Drill B: 2x2 mixed.
Drill C: when-NOT DFS.