01 Matrix

▶

Steps

setup

Initialize distance matrix with infinity

Create a distance matrix of the same size as input, setting all cells to infinity initially.

💡 This sets a baseline so we can update distances only when we find shorter paths.

Line:

dist = [[float('inf')] * n for _ in range(m)]

💡 All distances start as very large values, representing unknown distances.

setup

Set distance to 0 for zero cells

Scan the input matrix and set distance to 0 for cells that contain 0.

💡 Zero cells are the sources; their distance to zero is zero itself.

Line:

if mat[i][j] == 0:
    dist[i][j] = 0

💡 Distance matrix now reflects known zero distances at zero cells.

fill_cells

First pass: update (0,0) using top and left neighbors

At cell (0,0), no top or left neighbors exist, so distance remains 0.

💡 Edges of the matrix have no top or left neighbors, so their distances stay as initialized.

Line:

if i > 0:
    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
if j > 0:
    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

💡 Boundary cells keep their initial distances in first pass.

fill_cells

First pass: update (0,1) using top and left neighbors

At cell (0,1), no top neighbor, left neighbor (0,0) has distance 0, so update distance to min(inf, 0+1)=1 but current is 0, so stays 0.

💡 Left neighbor can reduce distance if smaller, but here distance is already 0.

Line:

if i > 0:
    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
if j > 0:
    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

💡 Distances do not increase if already minimal.

fill_cells

First pass: update (1,1) using top and left neighbors

At cell (1,1), top neighbor (0,1) distance 0, left neighbor (1,0) distance 0, so update distance to min(inf, 0+1, 0+1) = 1.

💡 This is the first cell with 1 in input; neighbors provide shortest distance 1.

Line:

if i > 0:
    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
if j > 0:
    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

💡 Distances propagate from zero cells to adjacent ones.

fill_cells

First pass: update (2,0) using top and left neighbors

At cell (2,0), top neighbor (1,0) distance 0, no left neighbor, update distance to min(inf, 0+1) = 1.

💡 Distances propagate downwards from zero cells.

Line:

if i > 0:
    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
if j > 0:
    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

💡 First pass propagates distances top-left to bottom-right.

fill_cells

First pass: update (2,1) using top and left neighbors

At cell (2,1), top neighbor (1,1) distance 1, left neighbor (2,0) distance 1, update distance to min(inf, 1+1, 1+1) = 2.

💡 Distances accumulate as we move away from zero cells.

Line:

if i > 0:
    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
if j > 0:
    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

💡 Distance values reflect shortest path to nearest zero.

fill_cells

First pass: update (2,2) using top and left neighbors

At cell (2,2), top neighbor (1,2) distance 0, left neighbor (2,1) distance 2, update distance to min(inf, 0+1, 2+1) = 1.

💡 Neighbor with smaller distance dominates the update.

Line:

if i > 0:
    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
if j > 0:
    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

💡 Distance updates pick the minimal neighbor path.

fill_cells

Second pass: update (2,2) using bottom and right neighbors

At cell (2,2), no bottom or right neighbors, distance remains 1.

💡 Bottom-right corner cells have no neighbors to update from in second pass.

Line:

if i < m - 1:
    dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)
if j < n - 1:
    dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)

💡 Second pass updates propagate from bottom-right to top-left.

fill_cells

Second pass: update (2,1) using bottom and right neighbors

At cell (2,1), right neighbor (2,2) distance 1, no bottom neighbor, update distance to min(2, 1+1) = 2 (no change).

💡 Right neighbor can reduce distance if smaller, but here distance stays the same.

Line:

if i < m - 1:
    dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)
if j < n - 1:
    dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)

💡 Second pass confirms or improves distances from bottom-right neighbors.

fill_cells

Second pass: update (1,1) using bottom and right neighbors

At cell (1,1), bottom neighbor (2,1) distance 2, right neighbor (1,2) distance 0, update distance to min(1, 2+1, 0+1) = 1 (no change).

💡 Right neighbor with smaller distance keeps distance at 1.

Line:

if i < m - 1:
    dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)
if j < n - 1:
    dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)

💡 Second pass ensures minimal distances from all directions.

fill_cells

Second pass: update (0,0) using bottom and right neighbors

At cell (0,0), bottom neighbor (1,0) distance 0, right neighbor (0,1) distance 0, update distance to min(0, 0+1, 0+1) = 0 (no change).

💡 Edges confirm zero distances remain zero.

Line:

if i < m - 1:
    dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)
if j < n - 1:
    dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)

💡 Second pass does not increase distances.

reconstruct

Final state: completed distance matrix

All cells have updated distances representing shortest distance to nearest zero cell.

💡 The matrix now correctly shows distances for all cells.

Line:

return dist

💡 Two-pass dynamic programming efficiently computes shortest distances.

from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        dist = [[float('inf')] * n for _ in range(m)]  # STEP 1: Initialize distances
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0  # STEP 2: Set zero distances
        for i in range(m):
            for j in range(n):
                if i > 0:
                    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)  # STEP 3-8: First pass top-left to bottom-right
                if j > 0:
                    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                if i < m - 1:
                    dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)  # STEP 9-12: Second pass bottom-right to top-left
                if j < n - 1:
                    dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)
        return dist  # STEP 13: Return final distances

📊

01 Matrix - Watch the Algorithm Execute, Step by Step

Watching each update step reveals how distances propagate through the matrix, making the dynamic programming approach intuitive and clear.

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: 0,0

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: 0,1

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: 1,1

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: 2,0

2,0

2,1

2,2

0,0

0,1

0,2

1,0

1,1

1,2

Visiting: 2,1

2,1

2,2

0,0

0,1

0,2

1,0

1,1

1,2

2,0

Visiting: 2,2

2,2

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

Visiting: 2,2

2,2

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

Visiting: 2,1

2,1

2,2

0,0

0,1

0,2

1,0

1,1

1,2

2,0

Visiting: 1,1

1,1

2,1

2,2

0,0

0,1

0,2

1,0

1,2

2,0

Visiting: 0,0

0,0

1,0

0,1

0,2

1,1

1,2

2,0

2,1

2,2

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Key Takeaways

✓ The two-pass dynamic programming approach efficiently computes shortest distances from zero cells without explicit BFS or DFS.

This insight is hard to see from code alone because the distance updates look like simple min operations, but watching the propagation clarifies the logic.

✓ The first pass propagates distances from top-left to bottom-right, and the second pass refines them from bottom-right to top-left.

Seeing the order of updates visually helps understand why two passes are necessary to capture all neighbor influences.

✓ Distance values never increase during updates; they only decrease or stay the same, ensuring convergence to minimal distances.

Watching each update step shows how the algorithm maintains and improves distance estimates, which is less obvious from static code.

Practice

1. Consider the following Python code implementing flood fill using DFS. Given the input image = [[1,1,1],[1,1,0],[1,0,1]], starting pixel (sr=1, sc=1), and newColor=2, what is the final image returned?

easy

A. [[1,1,1],[1,2,0],[1,0,1]]

B. [[2,2,2],[2,2,0],[2,0,2]]

C. [[2,2,2],[2,2,0],[2,0,1]]

D. [[2,2,2],[2,2,2],[2,2,2]]

Solution

1. Step 1: Trace dfs starting at (1,1) with original color=1

   The pixel at (1,1) is recolored to 2. Its neighbors with color 1 are (0,1), (2,1) is 0 so skipped, (1,0), and (1,2) is 0 skipped.

2. Step 2: Recursively recolor connected pixels with color 1

   All connected pixels with color 1 reachable from (1,1) are recolored to 2, resulting in [[2,2,2],[2,2,0],[2,0,1]]. The pixel at (2,2) remains 1 as it is not connected 4-directionally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only connected pixels with original color changed [OK]

Hint: Trace DFS calls carefully to find connected pixels [OK]

Common Mistakes:

• Changing pixels diagonally connected
• Forgetting to check boundaries

2. What is the time complexity of the optimal Dijkstra-based algorithm for finding the cheapest flight within K stops, given n cities and E flights? Assume the graph is represented as adjacency lists and a min-heap is used. A) O(n^2) because we may visit all nodes multiple times. B) O(E log E) because each edge can be pushed into the heap once. C) O(n log n) because Dijkstra runs in that time on sparse graphs. D) O(K * E) because we relax edges up to K times.

medium

A. O(n^2) because we may visit all nodes multiple times.

B. O(K * E) because we relax edges up to K times.

C. O(E log E) because each edge can be pushed into the heap once.

D. O(n log n) because Dijkstra runs in that time on sparse graphs.

Solution

1. Step 1: Identify heap operations

   Each edge can be pushed into the heap at most once per stops count, but stops ≤ K limits pushes. The heap size is bounded by O(E).

2. Step 2: Analyze complexity

   Each push/pop operation costs O(log E), so total time is O(E log E). The stops constraint prevents exponential blowup.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap operations dominate; stops limit expansions [OK]

Hint: Heap operations on edges dominate complexity [OK]

Common Mistakes:

• Assuming O(n^2) from classic Dijkstra on adjacency matrix
• Ignoring that stops limit expansions
• Confusing Bellman-Ford complexity with this approach

3. Examine the following code snippet implementing the Network Delay Time using Bellman-Ford. Which line contains a subtle bug that can cause incorrect results on graphs with unreachable nodes?

medium

A. Line 5: Missing check if dist[u] is infinity before relaxation

B. Line 7: Incorrect comparison operator in relaxation condition

C. Line 10: Breaking early when no updates is incorrect

D. Line 12: Returning -1 instead of max distance is wrong

Solution

1. Step 1: Analyze relaxation condition at line 5

   It lacks a check if dist[u] is infinity, so dist[u] + w can be infinity + w, causing incorrect updates.

2. Step 2: Other lines are correct: early break optimizes, comparison operator is correct, and returning -1 for unreachable nodes is expected

   Thus, the bug is the missing dist[u] != infinity check before relaxation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing dist[u] check causes invalid relaxation [OK]

Hint: Always check dist[u] != infinity before relaxing edges [OK]

Common Mistakes:

• Forgetting to check dist[u] before relaxation
• Misunderstanding early break optimization
• Incorrectly handling unreachable nodes

4. Suppose the Keys and Rooms problem is modified so that keys can be reused infinitely (i.e., you can revisit rooms multiple times). Which of the following changes to the algorithm is necessary to correctly determine if all rooms can be visited?

hard

A. Remove the visited array and perform DFS without tracking visited rooms

B. Use BFS with a queue and mark rooms as visited when enqueued to avoid infinite loops

C. Keep the visited array but reset it after each DFS call to allow revisits

D. Use a counter to limit the number of visits per room to prevent infinite recursion

Solution

1. Step 1: Understand infinite reuse of keys means cycles are possible

   Without marking visited before enqueueing, BFS can enqueue the same room multiple times causing inefficiency or infinite loops.

2. Step 2: Use BFS with visited marking on enqueue

   Marking visited when enqueuing prevents multiple enqueues of the same room, ensuring termination and correctness.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses progress; limiting visits is inefficient and complex.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS with visited marking on enqueue is standard for graphs with cycles [OK]

Hint: Mark visited when enqueuing in BFS to handle cycles [OK]

Common Mistakes:

• Removing visited causes infinite loops
• Resetting visited loses track of progress
• Counting visits is inefficient and unnecessary

5. Suppose the problem changes: fresh oranges can become rotten multiple times, and rot can spread back to previously rotten oranges if it results in a faster rot time. Which modification to the DFS-based solution correctly handles this scenario?

hard

A. Switch to a brute force simulation updating the grid minute by minute until no changes

B. Keep the original DFS with pruning but run it multiple times until no updates occur

C. Use a multi-source BFS but do not track times, just mark visited once

D. Remove the pruning condition that skips DFS if time_grid[r][c] <= time, allowing revisits with better times

Solution

1. Step 1: Understand new rot dynamics

   Rot can improve previously recorded rot times, so pruning based on time_grid[r][c] <= time is invalid.

2. Step 2: Modify DFS to allow revisits with better times

   Removing pruning condition enables DFS to update time_grid when a faster rot path is found.

3. Step 3: Confirm correctness

   This ensures all cells have minimum rot times even if rot spreads back to previously rotten oranges.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing revisits with better times handles dynamic rot spread correctly [OK]

Hint: Allow revisits if they improve rot time [OK]

Common Mistakes:

• Keeping pruning causes stale times
• Using BFS without time tracking
• Brute force is inefficient