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:
-
We first create an auxiliary matrix (
ans
) of the same dimensions as the input matrixmat
, 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. -
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).
-
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 ifans[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. -
After updating the distance of a neighboring cell, we enqueue it to the queue to later inspect its neighbors too.
-
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:
-
Matrix Initialization: An auxiliary matrix
ans
with the same dimensions as the input matrixmat
is created. Each cell inans
is initialized to-1
, except for the cells that correspond to0
inmat
; these are set to0
. The reason for using-1
is to indicate that a cell's distance to the nearest0
hasn't been calculated yet. -
Queue Initialization: A queue named
q
is used to store the cells which distances we want to calculate. All the positions of cells that contain0
in the original matrixmat
are put into the queue first. These serve as the starting points for the BFS since they are already0
and don't need their distances calculated. -
BFS Implementation: The algorithm dequeues an element
(i, j)
fromq
and looks at each of its four neighboring cells. By using thedirs
tuple, which is(-1, 0, 1, 0, -1)
, we can consider all four directions - up, down, left, and right by pairingdirs
elements using thepairwise
utility (this utility pairs elements such that we get pairs for all adjacent directions). -
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 ifans[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.
- It then iterates through these adjacent cells
-
Termination: The BFS process continues by repeatedly dequeuing, inspecting, updating, and enqueuing until the queue
q
is empty. At that point, the matrixans
contains the minimum distances of all cells to the nearest0
.
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 0
s 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 EvaluatorExample 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.
- Matrix Initialization: Create
ans
matrix of the same dimensions with-1
for all cells except cells corresponding to0
inmat
:
1ans = [ 2 [0, 0, -1], 3 [-1, -1, -1], 4 [-1, -1, 0] 5]
- Queue Initialization: Initialize the queue
q
with the coordinates of all0
s frommat
:
1q = [(0, 0), (0, 1), (2, 2)]
-
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 theirans
values need to be updated. -
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 already0
, we skip it. No updates are needed as it's already processed. - Look at neighbor
(1, 0)
. It's within the bounds andans[1][0]
is-1
, thus it hasn't been visited. We updateans[1][0]
to1
(asans[0][0] + 1
) and enqueue(1, 0)
:
- For the element
1ans = [ 2 [0, 0, -1], 3 [1, -1, -1], 4 [-1, -1, 0] 5] 6q = [(0, 1), (2, 2), (1, 0)]
-
Continue BFS: Follow the BFS algorithm until
q
is empty, updatingans
as you go. The final iterations will proceed as follows:(0, 1)
is skipped since it's a0
.(2, 2)
is a0
, 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]
- Termination: The final
ans
matrix now contains the distance to the nearest0
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 takesO(m * n)
time wherem
is the number of rows, andn
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, usesO(m * n)
space. -
The queue
q
can store a maximum ofm * n
positions (in the worst case when all elements are zero), which also takesO(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.
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
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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.