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.

Flowchart Walkthrough

To determine the appropriate algorithm for solving LeetCode 542. 01 Matrix, let's use the Flowchart. Here's a step-by-step analysis:

Is it a graph?

  • Yes: The matrix can be interpreted as a graph where each cell is a node connected to its neighbors (up, down, left, right).

Is it a tree?

  • No: A matrix typically represents a grid, not a hierarchical structure like a tree.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: The matrix is more about distances and connections, not about directed graphs without cycles.

Is the problem related to shortest paths?

  • Yes: The task is to find the minimum distances to the nearest zero for all cells, which aligns with finding shortest paths in each node's local neighborhood.

Is the graph weighted?

  • No: The graph implied by the matrix is unweighted as moving from one cell to the adjacent ones has equal cost or distance, typically considered as 1 per move.

Conclusion: Since the matrix represents an unweighted graph and the problem is to find shortest paths, the flowchart suggests using BFS (Breadth-First Search), which is efficient for exploring each level or layer of the graph uniformly, making it ideal for an unweighted shortest path search.

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.

Learn more about Breadth-First Search and Dynamic Programming patterns.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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.

Solution Implementation

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
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
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
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).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

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

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.