01 Matrix

🎯

01 Matrix

mediumGRAPHAmazonFacebookGoogle

Imagine you are mapping a city grid where some blocks have zero distance to a hospital, and you want to find the shortest distance from every block to the nearest hospital.

💡 This problem involves finding shortest distances on a grid, which can be tricky because beginners often try to compute distances from each cell independently, leading to inefficient solutions. Understanding multi-source BFS helps solve it efficiently.

📋

Problem Statement

Given an m x n binary matrix mat, return a matrix of the same dimensions where each cell contains the distance to the nearest 0 in the original matrix. The distance between two adjacent cells is 1.

m == mat.lengthn == mat[i].length1 ≤ m, n ≤ 10^41 ≤ m * n ≤ 10^5mat[i][j] is either 0 or 1There is at least one 0 in mat

💡

Example

Input"[[0,0,0],[0,1,0],[0,0,0]]"

Output[[0,0,0],[0,1,0],[0,0,0]]

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

Input"[[0,0,0],[0,1,0],[1,1,1]]"

Output[[0,0,0],[0,1,0],[1,2,1]]

Distances are computed as shortest path to nearest 0.

• Matrix with all zeros → output is the same matrix
• Matrix with a single zero and all other ones → distances increase outward
• Matrix with only one cell (0 or 1) → output is 0 if cell is 0, else distance to zero
• Large matrix with zeros clustered in one corner → distances grow as you move away

⚠️

Common Mistakes

Not initializing distances properly

Incorrect distances or infinite loops

✅ Initialize distances to infinity except zero cells

Using DFS instead of BFS

Incorrect distances because DFS does not guarantee shortest path

✅ Use BFS for shortest path in unweighted graphs

Not checking boundaries when exploring neighbors

Index out of bounds runtime errors

✅ Always check if neighbor indices are within matrix bounds

Re-enqueueing cells unnecessarily

Increased runtime and possible infinite loops

✅ Only enqueue neighbors when their distance is updated to a smaller value

Using a queue that is inefficient for BFS

Slower runtime due to costly operations

✅ Use deque in Python or LinkedList in Java for O(1) enqueue/dequeue

🧠

Brute Force (Check Each Cell Independently)

💡 This approach exists to build intuition by directly applying the problem definition, even though it is inefficient. It helps understand why BFS is needed.

Intuition

For each cell with value 1, scan the entire matrix to find the nearest 0 and record the minimum distance.

Algorithm

1. Initialize an output matrix with large values for all cells.
2. For each cell in the matrix:
3. If the cell is 0, set output cell to 0.
4. If the cell is 1, scan the entire matrix to find the nearest 0 and update output cell with the minimum distance.

💡 The nested scanning makes it hard to see efficiency, but it directly follows the problem statement.

</>

Code

from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        res = [[float('inf')] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    res[i][j] = 0
                else:
                    for x in range(m):
                        for y in range(n):
                            if mat[x][y] == 0:
                                dist = abs(i - x) + abs(j - y)
                                if dist < res[i][j]:
                                    res[i][j] = dist
        return res

# Driver code
if __name__ == '__main__':
    sol = Solution()
    mat = [[0,0,0],[0,1,0],[1,1,1]]
    print(sol.updateMatrix(mat))

Line Notes

m, n = len(mat), len(mat[0])Determine matrix dimensions for iteration limits

res = [[float('inf')] * n for _ in range(m)]Initialize result with infinity to find minimum distances

if mat[i][j] == 0:If current cell is zero, distance is zero

for x in range(m):Scan entire matrix to find zeros for distance calculation

import java.util.*;

public class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    res[i][j] = 0;
                } else {
                    res[i][j] = Integer.MAX_VALUE;
                    for (int x = 0; x < m; x++) {
                        for (int y = 0; y < n; y++) {
                            if (mat[x][y] == 0) {
                                int dist = Math.abs(i - x) + Math.abs(j - y);
                                if (dist < res[i][j]) res[i][j] = dist;
                            }
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] res = sol.updateMatrix(mat);
        System.out.println(Arrays.deepToString(res));
    }
}

Line Notes

int m = mat.length, n = mat[0].length;Get matrix dimensions for loops

if (mat[i][j] == 0)Set distance zero for zero cells

res[i][j] = Integer.MAX_VALUE;Initialize distances to max for comparison

for (int x = 0; x < m; x++)Nested loops to find nearest zero for each cell

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> res(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    res[i][j] = 0;
                } else {
                    for (int x = 0; x < m; x++) {
                        for (int y = 0; y < n; y++) {
                            if (mat[x][y] == 0) {
                                int dist = abs(i - x) + abs(j - y);
                                if (dist < res[i][j]) res[i][j] = dist;
                            }
                        }
                    }
                }
            }
        }
        return res;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> mat = {{0,0,0},{0,1,0},{1,1,1}};
    vector<vector<int>> res = sol.updateMatrix(mat);
    for (auto &row : res) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

int m = mat.size(), n = mat[0].size();Get matrix dimensions for iteration

vector<vector<int>> res(m, vector<int>(n, INT_MAX));Initialize result with max int for min distance search

if (mat[i][j] == 0)Distance zero for zero cells

for (int x = 0; x < m; x++)Nested loops to find nearest zero for each cell

var updateMatrix = function(mat) {
    const m = mat.length, n = mat[0].length;
    const res = Array.from({length: m}, () => Array(n).fill(Infinity));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 0) {
                res[i][j] = 0;
            } else {
                for (let x = 0; x < m; x++) {
                    for (let y = 0; y < n; y++) {
                        if (mat[x][y] === 0) {
                            const dist = Math.abs(i - x) + Math.abs(j - y);
                            if (dist < res[i][j]) res[i][j] = dist;
                        }
                    }
                }
            }
        }
    }
    return res;
};

// Test
console.log(updateMatrix([[0,0,0],[0,1,0],[1,1,1]]));

Line Notes

const m = mat.length, n = mat[0].length;Determine matrix size for loops

const res = Array.from({length: m}, () => Array(n).fill(Infinity));Initialize result with Infinity for min distance updates

if (mat[i][j] === 0)Distance zero for zero cells

for (let x = 0; x < m; x++)Nested loops to find nearest zero for each cell

⏱

Complexity

TimeO(m^2 * n^2)

SpaceO(m * n)

For each cell, scanning entire matrix leads to nested loops of size m*n each, resulting in O(m^2 * n^2).

💡 For a 100x100 matrix, this means 100 million operations, which is too slow for interviews.

Interview Verdict: TLE

This approach times out on large inputs, showing the need for a more efficient method like BFS.

🧠

Multi-Source BFS

💡 This approach improves efficiency by starting BFS simultaneously from all zero cells, spreading outwards to find minimum distances.

Intuition

Treat all zero cells as sources and perform BFS to update distances of neighboring cells layer by layer.

Algorithm

1. Initialize a queue and enqueue all cells with 0, setting their distance to 0.
2. Set distance for other cells to infinity initially.
3. While queue is not empty, dequeue a cell and check its neighbors.
4. If neighbor distance can be minimized, update it and enqueue the neighbor.

💡 The BFS ensures shortest distances because it explores neighbors in increasing order of distance.

</>

Code

from typing import List
from collections import deque

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)]
        q = deque()
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0
                    q.append((i, j))
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        while q:
            x, y = q.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    if dist[nx][ny] > dist[x][y] + 1:
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
        return dist

# Driver code
if __name__ == '__main__':
    sol = Solution()
    mat = [[0,0,0],[0,1,0],[1,1,1]]
    print(sol.updateMatrix(mat))

Line Notes

dist = [[float('inf')] * n for _ in range(m)]Initialize distances to infinity for all cells

if mat[i][j] == 0:Enqueue all zero cells as BFS starting points

directions = [(1,0), (-1,0), (0,1), (0,-1)]Define four possible neighbor directions

if dist[nx][ny] > dist[x][y] + 1:Update neighbor distance only if a shorter path is found

import java.util.*;

public class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.offer(new int[]{i, j});
                }
            }
        }
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int x = cell[0], y = cell[1];
            for (int[] d : directions) {
                int nx = x + d[0], ny = y + d[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    if (dist[nx][ny] > dist[x][y] + 1) {
                        dist[nx][ny] = dist[x][y] + 1;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] res = sol.updateMatrix(mat);
        System.out.println(Arrays.deepToString(res));
    }
}

Line Notes

int[][] dist = new int[m][n];Create distance matrix

Arrays.fill(row, Integer.MAX_VALUE);Initialize distances to max value

q.offer(new int[]{i, j});Add zero cells to BFS queue

if (dist[nx][ny] > dist[x][y] + 1)Relax neighbor distance if shorter path found

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        queue<pair<int,int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        vector<pair<int,int>> directions = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            for (auto& d : directions) {
                int nx = x + d.first, ny = y + d.second;
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    if (dist[nx][ny] > dist[x][y] + 1) {
                        dist[nx][ny] = dist[x][y] + 1;
                        q.push({nx, ny});
                    }
                }
            }
        }
        return dist;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> mat = {{0,0,0},{0,1,0},{1,1,1}};
    vector<vector<int>> res = sol.updateMatrix(mat);
    for (auto &row : res) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> dist(m, vector<int>(n, INT_MAX));Initialize distance matrix with max int

if (mat[i][j] == 0)Set distance zero for zero cells and enqueue

queue<pair<int,int>> q;Queue to perform BFS

if (dist[nx][ny] > dist[x][y] + 1)Update neighbor distance if shorter path found

var updateMatrix = function(mat) {
    const m = mat.length, n = mat[0].length;
    const dist = Array.from({length: m}, () => Array(n).fill(Infinity));
    const q = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 0) {
                dist[i][j] = 0;
                q.push([i, j]);
            }
        }
    }
    const directions = [[1,0],[-1,0],[0,1],[0,-1]];
    while (q.length) {
        const [x, y] = q.shift();
        for (const [dx, dy] of directions) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                if (dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push([nx, ny]);
                }
            }
        }
    }
    return dist;
};

// Test
console.log(updateMatrix([[0,0,0],[0,1,0],[1,1,1]]));

Line Notes

const dist = Array.from({length: m}, () => Array(n).fill(Infinity));Initialize distance matrix with Infinity

if (mat[i][j] === 0)Set zero cells distance to zero and enqueue

const q = [];Queue for BFS traversal

if (dist[nx][ny] > dist[x][y] + 1)Relax neighbor distance if shorter path found

⏱

Complexity

TimeO(m * n)

SpaceO(m * n)

Each cell is enqueued and processed at most once, so BFS runs in linear time relative to matrix size.

💡 For a 100x100 matrix, this means about 10,000 operations, which is efficient for interviews.

Interview Verdict: Accepted

This is the optimal and accepted approach for this problem in interviews.

🧠

Dynamic Programming (Two Passes)

💡 This approach uses DP to propagate minimum distances by scanning the matrix twice, which is an alternative to BFS.

Intuition

First pass updates distances based on top and left neighbors, second pass updates based on bottom and right neighbors.

Algorithm

1. Initialize distance matrix with large values except zero cells set to 0.
2. First pass: iterate from top-left to bottom-right, update distance using top and left neighbors.
3. Second pass: iterate from bottom-right to top-left, update distance using bottom and right neighbors.
4. Return the updated distance matrix.

💡 Two passes ensure distances are minimized considering all directions.

</>

Code

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)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0
        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)
                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)
                if j < n - 1:
                    dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)
        return dist

# Driver code
if __name__ == '__main__':
    sol = Solution()
    mat = [[0,0,0],[0,1,0],[1,1,1]]
    print(sol.updateMatrix(mat))

Line Notes

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

if mat[i][j] == 0:Set zero cells distance to zero

dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)Update distance using top neighbor in first pass

dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)Update distance using bottom neighbor in second pass

import java.util.*;

public class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE - 100000);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) dist[i][j] = 0;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) dist[i][j] = Math.min(dist[i][j], dist[i-1][j] + 1);
                if (j > 0) dist[i][j] = Math.min(dist[i][j], dist[i][j-1] + 1);
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i < m - 1) dist[i][j] = Math.min(dist[i][j], dist[i+1][j] + 1);
                if (j < n - 1) dist[i][j] = Math.min(dist[i][j], dist[i][j+1] + 1);
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] mat = {{0,0,0},{0,1,0},{1,1,1}};
        int[][] res = sol.updateMatrix(mat);
        System.out.println(Arrays.deepToString(res));
    }
}

Line Notes

Arrays.fill(row, Integer.MAX_VALUE - 100000);Initialize distances with large value avoiding overflow

if (mat[i][j] == 0) dist[i][j] = 0;Set zero cells distance to zero

dist[i][j] = Math.min(dist[i][j], dist[i-1][j] + 1);Update distance using top neighbor in first pass

dist[i][j] = Math.min(dist[i][j], dist[i+1][j] + 1);Update distance using bottom neighbor in second pass

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX - 100000));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) dist[i][j] = 0;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                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);
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                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);
            }
        }
        return dist;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> mat = {{0,0,0},{0,1,0},{1,1,1}};
    vector<vector<int>> res = sol.updateMatrix(mat);
    for (auto &row : res) {
        for (auto &val : row) cout << val << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> dist(m, vector<int>(n, INT_MAX - 100000));Initialize distances with large value to avoid overflow

if (mat[i][j] == 0) dist[i][j] = 0;Set zero cells distance to zero

dist[i][j] = min(dist[i][j], dist[i-1][j] + 1);Update distance using top neighbor in first pass

dist[i][j] = min(dist[i][j], dist[i+1][j] + 1);Update distance using bottom neighbor in second pass

var updateMatrix = function(mat) {
    const m = mat.length, n = mat[0].length;
    const dist = Array.from({length: m}, () => Array(n).fill(Infinity));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (mat[i][j] === 0) dist[i][j] = 0;
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i > 0) dist[i][j] = Math.min(dist[i][j], dist[i-1][j] + 1);
            if (j > 0) dist[i][j] = Math.min(dist[i][j], dist[i][j-1] + 1);
        }
    }
    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i < m - 1) dist[i][j] = Math.min(dist[i][j], dist[i+1][j] + 1);
            if (j < n - 1) dist[i][j] = Math.min(dist[i][j], dist[i][j+1] + 1);
        }
    }
    return dist;
};

// Test
console.log(updateMatrix([[0,0,0],[0,1,0],[1,1,1]]));

Line Notes

const dist = Array.from({length: m}, () => Array(n).fill(Infinity));Initialize distance matrix with Infinity

if (mat[i][j] === 0) dist[i][j] = 0;Set zero cells distance to zero

dist[i][j] = Math.min(dist[i][j], dist[i-1][j] + 1);Update distance using top neighbor in first pass

dist[i][j] = Math.min(dist[i][j], dist[i+1][j] + 1);Update distance using bottom neighbor in second pass

⏱

Complexity

TimeO(m * n)

SpaceO(m * n)

Two passes over the matrix each take O(m*n), so total time is linear in matrix size.

💡 This approach is efficient and easy to implement for large matrices.

Interview Verdict: Accepted

This DP approach is accepted and often preferred for its simplicity and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 Multi-source BFS is the best approach to code in interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m^2 * n^2)	O(m * n)	No	N/A	Mention only - never code
2. Multi-Source BFS	O(m * n)	O(m * n)	No	Yes	Code this approach
3. Dynamic Programming (Two Passes)	O(m * n)	O(m * n)	No	Yes	Good alternative to BFS

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of the problem.Step 3: Explain why brute force is inefficient and introduce multi-source BFS.Step 4: Code the BFS solution carefully, explaining each step.Step 5: Discuss the DP two-pass approach as an alternative.Step 6: Test your code with edge cases and explain time/space complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of BFS on grids, ability to optimize naive solutions, and clarity in explaining multi-source BFS.

Common Follow-ups

• What if diagonal moves are allowed? → Update BFS directions to include diagonals.
• Can you do this in-place? → Yes, by modifying the input matrix carefully.

💡 These follow-ups test your flexibility in adapting BFS and space optimization skills.

🔍

Pattern Recognition

When to Use

1) Grid or matrix input, 2) Need shortest distance to multiple sources, 3) Unweighted edges, 4) Output distances or levels

Signature Phrases

distance to nearest 0grid with 0s and 1sshortest path in matrix

NOT This Pattern When

Single-source shortest path problems or DP on sequences are different patterns.

Similar Problems

Walls and Gates - similar multi-source BFS to find distance to gatesRotting Oranges - BFS spreading infection from multiple sourcesShortest Distance from All Buildings - BFS from multiple buildings to find shortest sum distance

Practice

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

Solution

1. Step 1: Trace trust_score updates

   For trust pairs [1,3] and [2,3]: trust_score[1] -= 1, trust_score[3] += 1; trust_score[2] -= 1, trust_score[3] += 1. Final trust_score = [0, -1, -1, 2].

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

   n=3, so n-1=2. Only person 3 has trust_score 2, so return 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Person 3 trusted by 2 others, trusts nobody [OK]

Hint: Trust score array sums trust and distrust correctly [OK]

Common Mistakes:

• Returning the person who trusts others
• Off-by-one indexing in trust_score
• Confusing trust_score values with counts

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

3. You are given a 2D grid representing land (1) and water (0). You need to find the largest connected group of land cells connected only horizontally or vertically. Which algorithmic approach guarantees finding the maximum size of such a connected land area efficiently?

easy

A. Graph traversal using Depth-First Search (DFS) or Breadth-First Search (BFS) to explore connected components

B. Dynamic Programming that stores maximum island size ending at each cell using previous computations

C. Greedy approach that expands from each land cell by always moving to the neighbor with the largest immediate value

D. Sorting all land cells by their coordinates and merging adjacent cells in sorted order

Solution

1. Step 1: Understand the problem as finding connected components in a grid graph

   Each land cell is a node connected to neighbors horizontally or vertically.

2. Step 2: Recognize that DFS or BFS explores all connected nodes in a component, allowing counting of island size

   Greedy or DP approaches do not guarantee exploring all connected cells correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph traversal is the standard method for connected components [OK]

Hint: Connected components in grids -> DFS or BFS [OK]

Common Mistakes:

• Thinking DP can solve connected components directly
• Assuming greedy expansion finds max island
• Confusing sorting with connectivity

4. What is the time complexity of the bidirectional BFS algorithm for finding the shortest path in an n x n binary matrix, assuming all cells are walkable (0)?

medium

A. O(n^4) because each BFS can explore all cells and edges

B. O(8^(n^2)) due to 8 possible moves from each cell

C. O(n^2) because BFS explores each cell at most once from both ends

D. O(n^3) because of nested loops over rows, columns, and directions

Solution

1. Step 1: Identify number of vertices and edges

   Grid has n^2 vertices; each vertex has up to 8 edges.

2. Step 2: Analyze BFS complexity

   BFS visits each vertex once; total edges processed is O(8*n^2) = O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional BFS halves search space but still O(n^2) [OK]

Hint: BFS in grid -> O(n²) due to vertices and edges [OK]

Common Mistakes:

• Confusing exponential moves with complexity
• Assuming nested loops multiply to n^3 or n^4

5. Suppose the graph edges can have negative weights but no negative cycles. Which algorithm modification or choice correctly computes the shortest network delay times from a start node?

hard

A. Use DFS with path relaxation and memoization to handle negative weights efficiently.

B. Use Dijkstra's algorithm with a priority queue as usual; it handles negative weights correctly.

C. Use BFS since negative weights can be ignored for shortest paths.

D. Use Bellman-Ford algorithm to relax edges repeatedly, detecting negative cycles if any.

Solution

1. Step 1: Recognize that Dijkstra's algorithm fails with negative weights because it assumes non-negative edge costs

   BFS cannot handle weighted edges properly, and DFS with memoization is inefficient and may not terminate correctly.

2. Step 2: Bellman-Ford algorithm is designed to handle negative weights and detect negative cycles by repeated edge relaxation

   It guarantees correct shortest paths if no negative cycles exist.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bellman-Ford handles negative weights safely [OK]

Hint: Bellman-Ford handles negative weights; Dijkstra does not [OK]

Common Mistakes:

• Using Dijkstra with negative weights incorrectly
• Assuming BFS works for weighted graphs
• Believing DFS with memoization is efficient here