542. 01 Matrix


Problem Description

The task is to find the distance to the nearest 0 for each cell in a given m x n binary matrix mat. A binary matrix is a matrix where each cell can either be a 0 or a 1. The distance is defined as the minimum number of adjacent cell steps (up, down, left, or right) needed to reach a cell with the value 0 from the current cell. For example, if you're moving from mat[i][j] to mat[i][j+1] or mat[i+1][j], that counts as a distance of 1. The problem requires us to populate and return a new matrix with the same dimensions as the input matrix, where each cell contains the distance to the nearest 0 in the original matrix.

Intuition

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The key intuition is that the BFS allows us to find the shortest path in unweighted graphs (or matrices, in this case), starting from a source node (or cell with a value of 0). The steps are as follows:

  1. We first create an auxiliary matrix (ans) of the same dimensions as the input matrix mat, where each cell is initialized to -1 except the ones corresponding to 0s in the original matrix, which are initialized to 0. This new matrix will eventually hold the distance of each cell to the nearest 0.

  2. We then use a queue to keep track of cells that we need to explore. Initially, we enqueue the coordinates of all cells with 0s, as their distance to the nearest 0 is already known (which is 0).

  3. Now we perform the BFS. We dequeue a cell (i, j) from the queue and look at its immediate neighbors (up, down, left, right). If a neighbor (x, y) has not been visited before (which we check by seeing if ans[x][y] is -1), we set its value to be one more than the dequeued cell (ans[i][j] + 1) since it's an adjacent cell.

  4. After updating the distance of a neighboring cell, we enqueue it to the queue to later inspect its neighbors too.

  5. This process continues until the queue is empty, meaning all cells have been visited and assigned the distance to the nearest 0.

By the end of this BFS, the ans matrix will contain the distances of all cells to their nearest 0 cell, as desired.

Solution Approach

The solution provided follows a multi-source Breadth-First Search (BFS) approach. Here’s a step-by-step walkthrough:

  1. Matrix Initialization: An auxiliary matrix ans with the same dimensions as the input matrix mat is created. Each cell in ans is initialized to -1, except for the cells that correspond to 0 in mat; these are set to 0. The reason for using -1 is to indicate that a cell's distance to the nearest 0 hasn't been calculated yet.

  2. Queue Initialization: A queue named q is used to store the cells which distances we want to calculate. All the positions of cells that contain 0 in the original matrix mat are put into the queue first. These serve as the starting points for the BFS since they are already 0 and don't need their distances calculated.

  3. BFS Implementation: The algorithm dequeues an element (i, j) from q and looks at each of its four neighboring cells. By using the dirs tuple, which is (-1, 0, 1, 0, -1), we can consider all four directions - up, down, left, and right by pairing dirs elements using the pairwise utility (this utility pairs elements such that we get pairs for all adjacent directions).

  4. Neighbor Inspection and Update:

    • It then iterates through these adjacent cells (x, y) and checks if each is within the bounds of the matrix and if ans[x][y] is still set to -1.
    • If these conditions are met, we know we're looking at a cell whose shortest distance to a 0 hasn't been calculated yet.
    • The distance is then set to be 1 more than its neighbor (i, j) from which it was reached (ans[i][j] + 1).
    • The position (x, y) is then enqueued, which means its neighbors will be examined in the next iterations of BFS.
  5. Termination: The BFS process continues by repeatedly dequeuing, inspecting, updating, and enqueuing until the queue q is empty. At that point, the matrix ans contains the minimum distances of all cells to the nearest 0.

The use of BFS is key here because it guarantees that we update each cell with the minimum distance to 0. This happens because in BFS, we start updating distances from 0s themselves and move outward, ensuring that the first time a cell's distance is calculated, it is the shortest path. If we used Depth-First Search (DFS), we could end up visiting cells multiple times to update their distances, which would be inefficient.

Lastly, this implementation works efficiently since each cell is enqueued at most once, leading to a time complexity that is linear in the number of cells in the matrix, which is O(m*n) where m and n are the dimensions of the input matrix.

💪
Level Up Your
Algo Skills

Example Walkthrough

Given a binary matrix:

1mat = [
2  [0, 0, 1],
3  [1, 1, 1],
4  [1, 1, 0]
5]

Let's walk through the solution approach using this matrix.

  1. Matrix Initialization: Create ans matrix of the same dimensions with -1 for all cells except cells corresponding to 0 in mat:
1ans = [
2  [0, 0, -1],
3  [-1, -1, -1],
4  [-1, -1, 0]
5]
  1. Queue Initialization: Initialize the queue q with the coordinates of all 0s from mat:
1q = [(0, 0), (0, 1), (2, 2)]
  1. BFS Implementation: Since BFS uses a queue, we start by taking the first element in q, which is (0, 0) and explore its neighbors to see if their ans values need to be updated.

  2. Neighbor Inspection and Update:

    • For the element (0, 0) from the queue, it has two neighbors (0, 1) and (1, 0). Since (0, 1) is already 0, we skip it. No updates are needed as it's already processed.
    • Look at neighbor (1, 0). It's within the bounds and ans[1][0] is -1, thus it hasn't been visited. We update ans[1][0] to 1 (as ans[0][0] + 1) and enqueue (1, 0):
1ans = [
2  [0, 0, -1],
3  [1, -1, -1],
4  [-1, -1, 0]
5]
6q = [(0, 1), (2, 2), (1, 0)]
  1. Continue BFS: Follow the BFS algorithm until q is empty, updating ans as you go. The final iterations will proceed as follows:

    • (0, 1) is skipped since it's a 0.
    • (2, 2) is a 0, its neighbors are inspected and updated accordingly.
    • (1, 0) is dequeued next, updating its neighbors.
    • Repeat this process until q is empty.

By the end of BFS, q is emptied and the ans matrix is fully updated:

1ans = [
2  [0, 0, 1],
3  [1, 1, 1],
4  [2, 1, 0]
5]
  1. Termination: The final ans matrix now contains the distance to the nearest 0 for each cell, and we return this as the solution.

Python Solution

1from collections import deque
2
3class Solution:
4    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
5        # Get the matrix dimensions
6        rows, cols = len(matrix), len(matrix[0])
7        # Prepare an answer matrix with the same dimensions
8        distance_matrix = [[-1] * cols for _ in range(rows)]
9        # Initialize a queue to store the indices of 0s
10        queue = deque()
11      
12        # Go through the matrix to find all the 0s
13        for i in range(rows):
14            for j in range(cols):
15                if matrix[i][j] == 0:
16                    # Set the distance for 0s as 0
17                    distance_matrix[i][j] = 0
18                    # Add the coordinates of the 0 to the queue
19                    queue.append((i, j))
20
21        # Directions for moving up, left, down, right
22        directions = ((-1, 0), (0, -1), (1, 0), (0, 1))
23      
24        # Process the queue
25        while queue:
26            i, j = queue.popleft()
27            # Explore all neighboring cells in the four directions
28            for delta_i, delta_j in directions:
29                neighbor_i, neighbor_j = i + delta_i, j + delta_j
30                # If the neighbor is within bounds and hasn't been visited
31                if 0 <= neighbor_i < rows and 0 <= neighbor_j < cols and distance_matrix[neighbor_i][neighbor_j] == -1:
32                    # Update the distance for the neighbor
33                    distance_matrix[neighbor_i][neighbor_j] = distance_matrix[i][j] + 1
34                    # Add the neighbor's coordinates to the queue for further exploration
35                    queue.append((neighbor_i, neighbor_j))
36      
37        # Return the updated distance matrix
38        return distance_matrix
39

Java Solution

1class Solution {
2    public int[][] updateMatrix(int[][] matrix) {
3        // Get the dimensions of the matrix.
4        int rows = matrix.length, cols = matrix[0].length;
5      
6        // Create a matrix to store the answer with the same dimensions.
7        int[][] distanceMatrix = new int[rows][cols];
8      
9        // Initialize the distance matrix with -1 to mark as not processed.
10        for (int[] row : distanceMatrix) {
11            Arrays.fill(row, -1);
12        }
13      
14        // Create a queue to perform the BFS.
15        Deque<int[]> queue = new ArrayDeque<>();
16      
17        // Loop through every cell in the matrix.
18        for (int i = 0; i < rows; ++i) {
19            for (int j = 0; j < cols; ++j) {
20              
21                // If the current cell has a 0, mark same in the distance matrix, and add it to the queue.
22                if (matrix[i][j] == 0) {
23                    queue.offer(new int[] {i, j});
24                    distanceMatrix[i][j] = 0;
25                }
26            }
27        }
28      
29        // Array to help iterate over the 4 neighboring cells (up, right, down, left).
30        int[] directions = {-1, 0, 1, 0, -1};
31      
32        // Perform BFS on the queue until it's empty.
33        while (!queue.isEmpty()) {
34            // Poll an element from the queue
35            int[] position = queue.poll();
36            int currentRow = position[0], currentCol = position[1];
37          
38            // Iterate over the four possible neighbors of the current cell.
39            for (int k = 0; k < 4; ++k) {
40                int newRow = currentRow + directions[k], newCol = currentCol + directions[k + 1];
41              
42                // Check if the new cell is within bounds and hasn't been visited yet.
43                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && distanceMatrix[newRow][newCol] == -1) {
44                    // Update the distance matrix with the distance from the nearest 0.
45                    distanceMatrix[newRow][newCol] = distanceMatrix[currentRow][currentCol] + 1;
46                    // Add the new cell to the queue to continue the BFS.
47                    queue.offer(new int[] {newRow, newCol});
48                }
49            }
50        }
51      
52        // Return the updated distance matrix.
53        return distanceMatrix;
54    }
55}
56

C++ Solution

1class Solution {
2public:
3    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
4        int rows = matrix.size(); // Number of rows in the matrix
5        int cols = matrix[0].size(); // Number of columns in the matrix
6        vector<vector<int>> dist(rows, vector<int>(cols, -1)); // Initialize the distance matrix with -1
7        queue<pair<int, int>> queue; // Queue to store the matrix cells
8      
9        // Initialize the queue with all the cells that have 0s and set their distance to 0
10        for (int row = 0; row < rows; ++row) {
11            for (int col = 0; col < cols; ++col) {
12                if (matrix[row][col] == 0) {
13                    dist[row][col] = 0;
14                    queue.emplace(row, col);
15                }
16            }
17        }
18      
19        // Defining directions for easy access to adjacent cells in matrix (up, right, down, left)
20        vector<int> directions = {-1, 0, 1, 0, -1};
21
22        // Perform Breadth-First Search
23        while (!queue.empty()) {
24            pair<int, int> cur = queue.front(); // Get current cell from the queue
25            queue.pop();
26
27            // Check all adjacent cells
28            for (int i = 0; i < 4; ++i) { // Loop through all four possible directions
29                int nextRow = cur.first + directions[i];   // Compute row index for adjacent cell
30                int nextCol = cur.second + directions[i+1]; // Compute column index for adjacent cell
31
32                // Check if the adjacent cell is within bounds and hasn't been visited
33                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && dist[nextRow][nextCol] == -1) {
34                    // If the cell is valid and unvisited, calculate its distance and add to queue
35                    dist[nextRow][nextCol] = dist[cur.first][cur.second] + 1;
36                    queue.emplace(nextRow, nextCol);
37                }
38            }
39        }
40      
41        return dist; // Return the distance matrix after processing.
42    }
43};
44

Typescript Solution

1function updateMatrix(matrix: number[][]): number[][] {
2    // Dimension of the given matrix
3    const numRows: number = matrix.length;
4    const numCols: number = matrix[0].length;
5
6    // Initialize the answer matrix with -1,
7    // indicating that distances have not been calculated yet
8    const answerMatrix: number[][] = Array.from({ length: numRows }, () =>
9        Array(numCols).fill(-1));
10
11    // Queue to maintain the cells with value 0
12    const queue: [number, number][] = [];
13
14    // Populate the queue with all the cells that contain 0
15    // and update their distance in the answer matrix
16    for (let row = 0; row < numRows; ++row) {
17        for (let col = 0; col < numCols; ++col) {
18            if (matrix[row][col] === 0) {
19                queue.push([row, col]);
20                answerMatrix[row][col] = 0;
21            }
22        }
23    }
24
25    // Directions array to explore adjacent cells (up, right, down, left)
26    const directions: number[] = [-1, 0, 1, 0, -1];
27
28    // Process the queue and update each cell's distance from the nearest 0
29    while (queue.length > 0) {
30        const [currentRow, currentCol] = queue.shift()!;
31
32        // Explore the adjacent cells in 4 directions
33        for (let k = 0; k < 4; ++k) {
34            const nextRow = currentRow + directions[k];
35            const nextCol = currentCol + directions[k + 1];
36
37            // If the next cell is within bounds and its distance is not calculated
38            if (nextRow >= 0 && nextRow < numRows &&
39                nextCol >= 0 && nextCol < numCols &&
40                answerMatrix[nextRow][nextCol] === -1) {
41                // Update the distance and add the cell to the queue
42                answerMatrix[nextRow][nextCol] = answerMatrix[currentRow][currentCol] + 1;
43                queue.push([nextRow, nextCol]);
44            }
45        }
46    }
47
48    // Return the updated answer matrix
49    return answerMatrix;
50}
51

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the number of elements in the matrix and the operations performed on each of those elements. Here's a breakdown:

  • The nested for loops go through each element of the matrix to initialize the ans array and populate the queue with the positions of the zeroes, which takes O(m * n) time where m is the number of rows, and n is the number of columns in the matrix.

  • The while loop dequeues each position from the queue at most once. Since each element can be added to the queue only once, the while loop will have at most m * n iterations.

  • Inside the while loop, we iterate over the four possible directions from each position, which is a constant time operation.

Since the number of operations for each element is constant, the overall time complexity of this code is O(m * n).

Space Complexity

The space complexity is determined by the additional space used by the algorithm, not including the space for the input and output:

  • The ans array, which has the same dimensions as the input matrix, uses O(m * n) space.

  • The queue q can store a maximum of m * n positions (in the worst case when all elements are zero), which also takes O(m * n) space.

Therefore, the overall space complexity of the algorithm is O(m * n).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫