01 Matrix

📋

01 Matrix

Edge cases:

</>

IDE

def updateMatrix(mat: list[list[int]]) -> list[list[int]]:public int[][] updateMatrix(int[][] mat)vector<vector<int>> updateMatrix(vector<vector<int>>& mat)function updateMatrix(mat)

def updateMatrix(mat: list[list[int]]) -> list[list[int]]:
    # Write your solution here
    pass

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        // Write your solution here
        return new int[0][0];
    }
}

#include <vector>
using namespace std;

vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    // Write your solution here
    return {};
}

function updateMatrix(mat) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Distances too large or unchanged for some cellsUsing brute force approach checking each cell against all zeros, causing incorrect or incomplete updates.✅ Implement multi-source BFS starting from all zero cells simultaneously, updating neighbors with distance +1 only if smaller.

Wrong: All distances zero or unchanged from inputNot updating distances for cells with 1, or not initializing BFS queue with zero cells.✅ Initialize queue with all zero cells and set their distances to zero; update neighbors accordingly.

Wrong: Distances incorrect due to greedy approach picking first zero onlyUsing greedy method that assigns distance based on first zero found instead of shortest distance.✅ Use BFS to ensure shortest distance from any zero, not just first zero encountered.

Wrong: Distances incorrect due to treating problem as unbounded BFS or summing weights incorrectlyConfusing 0/1 BFS with unbounded BFS, leading to wrong distance calculations.✅ Use standard BFS with queue and update distances only if new distance is smaller.

✓

Test Cases

Try testing your solution on edge cases like all zeros or single zero surrounded by ones.

Consider tricky cases where greedy or partial BFS fails; test multiple zero sources.

Optimize your solution to run in O(m*n) time using multi-source BFS to handle large inputs.

t1_01basic

Input{"mat":[[0,0,0],[0,1,0],[0,0,0]]}

Expected[[0,0,0],[0,1,0],[0,0,0]]

⏱ Performance - must finish in 2000ms

All 1s are adjacent to 0s, so their distance is 1.

💡 Think about starting BFS from all zero cells simultaneously.

💡 Use a multi-source BFS to propagate distances to 1s.

💡 Initialize queue with all zeros and update neighbors with distance +1.

Why it failed: Output distances incorrect: likely not using multi-source BFS or not updating neighbors properly. Fix by initializing queue with all zeros and updating neighbors with distance +1 only if smaller.

✓ Correct multi-source BFS implementation producing accurate distances.

t1_02basic

Input{"mat":[[0,1,1],[1,1,1],[1,1,0]]}

Expected[[0,1,2],[1,2,1],[1,1,0]]

⏱ Performance - must finish in 2000ms

Distances propagate from zeros at (0,0) and (2,2) to all cells.

💡 Remember to update distances only if the new distance is smaller.

💡 Check all four directions (up, down, left, right) for neighbors.

💡 Use a queue to process cells in order of increasing distance.

Why it failed: Distances too large or unchanged: likely missing updates or not checking all neighbors. Fix by checking all four neighbors and updating only if new distance is smaller.

✓ Distances correctly computed using BFS from multiple zero sources.

t2_01edge

Input{"mat":[[0,0],[0,0]]}

Expected[[0,0],[0,0]]

⏱ Performance - must finish in 2000ms

All zeros, so distances remain zero.

💡 Check behavior when matrix contains only zeros.

💡 Distances should remain zero without any updates.

💡 Ensure BFS initialization handles all-zero matrix correctly.

Why it failed: Output changed zeros to non-zero distances: likely not handling zero cells as distance zero. Fix by initializing zero cells with distance zero and not updating them.

✓ Correctly returns zero distances for all-zero matrix.

t2_02edge

Input{"mat":[[1,1,1],[1,0,1],[1,1,1]]}

Expected[[2,1,2],[1,0,1],[2,1,2]]

⏱ Performance - must finish in 2000ms

Single zero in center, distances increase outward by Manhattan distance.

💡 Test single zero surrounded by ones.

💡 Distances should reflect Manhattan distance from the zero.

💡 Ensure BFS expands correctly from the single zero.

Why it failed: Distances incorrect or not increasing properly: likely BFS not expanding correctly or missing neighbors. Fix by correctly enqueueing neighbors and updating distances.

✓ Distances correctly reflect Manhattan distance from single zero.

t2_03edge

Input{"mat":[[0]]}

Expected[[0]]

⏱ Performance - must finish in 2000ms

Single cell zero, distance is zero.

💡 Check smallest possible matrix size.

💡 Distance for zero cell is zero.

💡 Ensure no errors on 1x1 input.

Why it failed: Output not zero for single zero cell: likely not handling single cell edge case. Fix by initializing zero cells with zero distance.

✓ Correctly handles single cell zero matrix.

t2_04edge

Input{"mat":[[0,0,0,0],[0,1,1,1],[0,1,1,1],[0,1,1,1]]}

Expected[[0,0,0,0],[0,1,2,3],[0,1,2,3],[0,1,2,3]]

⏱ Performance - must finish in 2000ms

Zeros clustered in one corner, distances grow as you move away.

💡 Test distances growing from clustered zeros.

💡 Ensure BFS propagates distances correctly in all directions.

💡 Check boundary conditions for edges far from zeros.

Why it failed: Distances incorrect or not increasing properly: likely BFS not propagating fully or missing updates. Fix by ensuring BFS visits all reachable cells and updates distances.

✓ Distances correctly increase from clustered zeros.

t3_01corner

Input{"mat":[[1,1,1],[1,1,1],[1,1,0]]}

Expected[[4,3,2],[3,2,1],[2,1,0]]

⏱ Performance - must finish in 2000ms

Distances increase correctly from single zero in corner.

💡 Beware of greedy approaches that assign distance based on first zero found.

💡 Use BFS to ensure shortest distance to any zero.

💡 Check all neighbors and update distances if smaller.

Why it failed: Distances too large or incorrect due to greedy approach picking first zero only. Fix by using multi-source BFS or full BFS from all zeros.

✓ Correct BFS ensures shortest distances from zero in corner.

t3_02corner

Input{"mat":[[1,0,1],[1,1,1],[1,1,1]]}

Expected[[1,0,1],[2,1,2],[3,2,3]]

⏱ Performance - must finish in 2000ms

Distances propagate correctly from zero in middle top row.

💡 Avoid confusing 0/1 BFS with unbounded BFS.

💡 Distances must be shortest path, not sum of weights.

💡 Use queue to propagate distances layer by layer.

Why it failed: Distances incorrect due to treating problem as unbounded BFS or summing weights incorrectly. Fix by using standard BFS with queue and updating distances only if smaller.

✓ Correct BFS traversal computes accurate shortest distances.

t3_03corner

Input{"mat":[[0,1,1,0,1],[1,1,1,1,1],[1,1,0,1,1]]}

Expected[[0,1,1,0,1],[1,2,1,1,2],[1,1,0,1,2]]

⏱ Performance - must finish in 2000ms

Multiple zeros scattered, distances computed correctly.

💡 Check BFS handles multiple zero sources correctly.

💡 Ensure distances updated only if new distance is smaller.

💡 Verify BFS queue initialization with all zeros.

Why it failed: Distances incorrect due to incomplete BFS initialization or missing updates. Fix by initializing queue with all zeros and updating neighbors properly.

✓ Multi-source BFS correctly computes distances from multiple zeros.

t4_01performance

Input{"mat":[[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large matrix with 100 rows and 1000 columns (total 100,000 cells). Multi-source BFS O(m*n) must complete within 2 seconds.

💡 Use multi-source BFS for O(m*n) time complexity.

💡 Avoid brute force checking each cell against all zeros.

💡 Use a queue and update distances only once per cell.

Why it failed: TLE due to brute force O(m^2*n^2) approach. Fix by implementing multi-source BFS with queue to achieve O(m*n) complexity.

✓ Efficient BFS completes within time limit.

Practice

1. You are given a list of courses and their prerequisite pairs. You need to determine if it is possible to finish all courses without running into a circular dependency. Which algorithmic approach guarantees an optimal solution to detect such cycles in the course dependency graph?

easy

A. Perform a topological sort using Kahn's Algorithm (BFS) to detect cycles by checking if all nodes can be processed.

B. Use a brute force approach that tries all possible course orders to find a valid sequence.

C. Apply dynamic programming to count the number of ways to complete courses without cycles.

D. Use a greedy algorithm that always picks the course with the fewest prerequisites first.

Solution

1. Step 1: Understand the problem as cycle detection in a directed graph

   The problem requires detecting if a cycle exists in the course prerequisite graph, which invalidates any course order.

2. Step 2: Identify the algorithm that detects cycles efficiently

   Kahn's Algorithm performs a topological sort using BFS and in-degree counts. If all nodes are processed, no cycle exists; otherwise, a cycle is detected.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Topological sort with BFS is the standard cycle detection method for this problem [OK]

Hint: Topological sort detects cycles by processing all nodes [OK]

Common Mistakes:

• Greedy approach fails on complex dependencies
• Dynamic programming is not suited for cycle detection
• Brute force is inefficient and impractical

2. Consider the following Python code implementing the optimal solution for the minimum effort path problem. Given the input heights = [[1,2,2],[3,8,2],[5,3,5]], what is the final returned minimum effort?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace initial steps

   Start at (0,0) with effort 0. From (0,0), neighbors are (1,0) with effort max(0,|1-3|)=2 and (0,1) with effort max(0,|1-2|)=1.

2. Step 2: Explore paths and update efforts

   Heap pops (0,0,1) with effort 1, then explores neighbors updating efforts. The minimal maximum effort path found is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Manual tracing confirms minimal effort is 2 [OK]

Hint: Trace heap pops and max edge efforts [OK]

Common Mistakes:

• Confusing sum of differences with max difference
• Off-by-one in indices
• Returning effort before reaching target

3. What is the time complexity of the optimal BFS approach for the Surrounded Regions problem on an m x n board?

medium

A. O(m * n) because each cell is visited at most once during BFS marking.

B. O(m * n * (m + n)) because each 'O' region is checked separately.

C. O(m * n * 4) due to checking four neighbors for each cell multiple times.

D. O(m + n) since only boundary cells are initially processed.

Solution

1. Step 1: Analyze BFS traversal

   Each cell is enqueued and dequeued at most once during BFS marking, so total operations are proportional to the number of cells, m*n.

2. Step 2: Consider neighbor checks

   Each cell checks up to 4 neighbors, but this is constant factor, so complexity remains O(m*n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear scan plus BFS over all cells is O(m*n) [OK]

Hint: BFS visits each cell once, so O(m*n) time [OK]

Common Mistakes:

• Confusing BFS with brute force approach leading to O(m*n*(m+n)).
• Counting neighbor checks as multiplicative rather than constant factor.
• Assuming only boundary cells matter for complexity.

4. Suppose the problem is modified so that the town judge can trust some people but must still be trusted by everyone else. Which modification to the optimal trust score approach correctly finds the judge?

hard

A. Use an in-degree array counting how many trust the person, and find person with in-degree n-1 regardless of out-degree

B. Only check for the person trusted by everyone else, ignoring if they trust others (trust_score[i] == n - 1 or more)

C. Keep the same trust score logic but check for trust_score[i] >= n - 1 instead of == n - 1

D. Use the original approach but add a second pass to verify the candidate trusts nobody

Solution

1. Step 1: Understand the relaxed condition

   The judge can trust others, so the original condition that judge trusts nobody is removed.

2. Step 2: Use in-degree only

   Count how many people trust each person (in-degree). The judge must have in-degree n-1 regardless of out-degree.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-degree array correctly identifies judge under relaxed trust condition [OK]

Hint: In-degree alone suffices if judge can trust others [OK]

Common Mistakes:

• Trying to use trust_score with equality check
• Ignoring out-degree but still checking it
• Adding unnecessary verification passes

5. Suppose the problem is modified so that water can flow uphill by at most 1 unit of height difference (i.e., from a cell to a neighbor if neighbor's height ≥ current height - 1). Which modification to the BFS approach correctly handles this variant?

hard

A. Change the BFS condition to allow neighbor heights >= current height - 1 and keep the rest unchanged.

B. No change needed; original BFS condition already covers uphill flow.

C. Run BFS from each cell individually to check uphill flow possibility.

D. Use a priority queue BFS (Dijkstra) to handle varying height constraints efficiently.

Solution

1. Step 1: Understand uphill flow constraint

   Allowing uphill flow by 1 unit means edges have weights or costs, not uniform.

2. Step 2: BFS is insufficient

   Standard BFS assumes uniform edge cost; to handle varying constraints, Dijkstra's algorithm with a priority queue is needed.

3. Step 3: Modify algorithm

   Use priority queue BFS (Dijkstra) to explore cells with minimal cost respecting height difference constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Uphill flow requires weighted graph traversal -> Dijkstra [OK]

Hint: Uphill flow needs weighted BFS -> Dijkstra [OK]

Common Mistakes:

• Trying to fix with simple BFS condition change
• Running BFS from every cell causes TLE