Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: 01 Matrix
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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<sup>4</sup>
  • 1 <= m * n <= 10<sup>4</sup>
  • 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
Image

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

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Best and Worst Case: O(m \times n)
    • 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, (m \times n), where (m) is the number of rows and (n) is the number of columns in the matrix.

Space Complexity

  • Worst Case: O(m \times n)
    • 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 O(m \times n) due to the queue storage.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible