Interview Prepgraphs-dfs-bfsmediumAmazonFacebookGoogle

01 Matrix

Choose your preparation mode4 modes available

Try It Solution Trace

</>

IDE

def updateMatrix(mat: list[list[int]]) -> list[list[int]]:

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
}

0/10

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

t1_01basic

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

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

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

t1_02basic

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

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

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

Practice

(1/5)

1. Consider the following Python code to find the town judge:

def findJudge(n, trust):
    trust_score = [0] * (n + 1)
    for a, b in trust:
        trust_score[a] -= 1
        trust_score[b] += 1
    for i in range(1, n + 1):
        if trust_score[i] == n - 1:
            return i
    return -1

print(findJudge(3, [[1,3],[2,3]]))

What is the output of this code?

easy

A. 1

B. -1

C. 3

D. 2

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

01 Matrix

Practice

Solution

Step 1: Trace trust_score updates

Step 2: Identify judge by trust_score == n-1

Final Answer:

Quick Check:

Solution

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

Step 2: Recursively recolor connected pixels with color 1

Final Answer:

Quick Check:

Solution

Step 1: Initialize in-degree and queue

Step 2: Process queue

Final Answer:

Quick Check:

Solution

Step 1: Mark Pacific border cells

Step 2: Fill pacific_reachable matrix

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in the algorithm

Step 2: Combine complexities

Final Answer:

Quick Check:

Ready to prove it?