DSA sheet · Graphs · Multi-source BFS pattern

01 Matrix

The teacher calls this the very first question of the BFS pattern in her sheet. It teaches two ideas we will reuse again and again: in a graph where every step costs 1, BFS gives shortest distances, and when there are many starting points, put all of them in the queue at the start (multi-source BFS). She also shows how a −1 in the distance grid can replace a separate visited array.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (graphs, BFS, grids)
• · inside Part 0: why BFS layers = shortest path
• · inside Part 0: multi-source BFS, and why all sources start together
• Part A · Multi-source BFS from every 0
• Part B · Revision page

Part 0 · Before starting

Nodes, edges, and kinds of graphs

A graph is a set of nodes (points) joined by edges (connections).

(0)—(1)        undirected: walk 0→1 or 1→0
(0)→(1)        directed:   only 0→1
(0)—7—(1)      weighted:   walking this edge costs 7

If no weights are given, every edge costs 1. That's called an unweighted graph, and the distance between two nodes is just "how many edges on the shortest route".

Storing a graph: edge list → adjacency list

Problems often give an edge list (pairs [u, v]) or an adjacency matrix (a table, 1 = edge). We usually build an adjacency list, which stores the neighbours of each node so we can quickly ask "where can I go from u?".

n = 4
edges = [[0, 1], [1, 2], [2, 3]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)          # undirected: both ways
print(adj)   # [[1], [0, 2], [1, 3], [2]]

A grid is a graph, with no adjacency list needed

Each cell (r, c) is a node. Its neighbours are the cells sharing a side with it. The teacher's reasoning: we build an adjacency list when we don't know who the children are. In a grid we do know: add one of four (row, column) offsets.

               (r-1, c)   dr,dc = (-1, 0)
                  ↑
(r, c-1)  ←    (r, c)    →  (r, c+1)       (0,-1) and (0, 1)
                  ↓
               (r+1, c)   (1, 0)

• Bounds check: only use (nr, nc) when 0 <= nr < rows and 0 <= nc < cols.
• Only 4 directions here. If diagonals were allowed the question would say so. You can also confirm it from the expected output (step 4 below).

Visited, and connected components

Graphs have loops: cell A's neighbour is B and B's neighbour is A. Without a visited mark, BFS would push them back and forth forever. A visited mark means "already reached, never push again". (A connected component is a group of nodes that can reach each other. In this problem every cell can reach every other, since there are no walls.)

BFS and DFS in one line each

• BFS (breadth first search): use a queue (collections.deque). Visit the start, then everything 1 step away, then 2 steps away… level by level.
• DFS (depth first search): use recursion or a stack. Go as deep as you can along one path, then back up and try the next.

from collections import deque

grid = [[0, 0, 0],
        [0, 0, 0]]
rows, cols = len(grid), len(grid[0])
dist = [[-1] * cols for _ in range(rows)]   # -1 = not visited
dist[0][0] = 0
queue = deque([(0, 0)])
while queue:
    r, c = queue.popleft()
    for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1     # mark when pushing
            queue.append((nr, nc))
print(dist)   # [[0, 1, 2], [1, 2, 3]]

Why BFS layers give the shortest path

BFS pops cells in order of distance: first all cells at distance 0, then all at 1, then all at 2. A new cell is always pushed at the back with distance (parent + 1), so the queue never has a distance d+2 cell in front of a distance d+1 cell.

queue over time:   [ d d d | d+1 d+1 ]  →  [ d+1 d+1 | d+2 ]  → ...
                     popping   pushed at back

So the first time a cell gets a distance, it is reached by the earliest layer that touches it. A shorter route would mean an earlier layer touched it, which would have set the distance earlier. That's why the first value is final and we never overwrite it. This only holds when every step costs the same. With different edge costs (weights) we'd need Dijkstra, which the teacher says comes later.

Multi-source BFS: why all sources start in the queue together

Normal BFS starts from one node. Multi-source BFS starts from many nodes at the same time: all of them go into the queue first, each with distance 0.

Picture several stones dropped into a pond at the same moment. Each makes a ripple. Where two ripples meet, a point gets wet by whichever ripple arrives first, which is the nearest stone. That's exactly "distance to the nearest source".

sources A and B in one row:      A . . . . B
all start together  (layer 0):   0 . . . . 0
layer 1:                         0 1 . . 1 0
layer 2:                         0 1 2 2 1 0     ← each cell got its NEAREST source

Now see what goes wrong if we start from only one source:

BFS from A only:                 0 1 2 3 4 5     ← the cell next to B says 4, real answer is 1
then from B, but cells are already visited, so they can't be fixed

• Starting from one source at a time gives wrong answers (if we keep visited) or costs a full BFS per source (if we reset and take the minimum each time, roughly O(sources × cells)).
• Starting all together keeps the "layers in order" rule: layer 0 is all sources, layer 1 is everything one step from any source, and so on. The first ripple to reach a cell comes from its nearest source. One BFS, correct answers.

Part A · Multi-source BFS from every 0

LeetCode 542

1The question in simple words

You get an m×n grid of 0s and 1s ("binary" matrix). For every cell, find how far the nearest 0 is. Moving to a cell that shares a side costs 1. Return a grid of these distances.

• A cell holding 0 is already on a 0, so its answer is 0.
• The real work is for the 1s.

input      output
0 0 0      0 0 0
0 1 0      0 1 0
0 0 0      0 0 0

input      output
0 0 0      0 0 0
0 1 0      0 1 0
1 1 1      1 2 1

Example 1 has one 1, and a 0 touches it, so its answer is 1. In Example 2, four of the 1s touch a 0 (answer 1), but the bottom-middle 1 has only 1s around it, so its answer is 2.

2What the constraints tell us

• 1 <= m, n <= 10⁴ and m · n <= 10⁴ → at most 10⁴ cells. A linear pass over the cells (times 4 directions) is tiny.
• Each cell is 0 or 1, and there is at least one 0 → every cell has an answer. We never need a "−1 = unreachable" result.
• Running a separate BFS from each 1 would be up to 10⁴ × 10⁴ = 10⁸ steps, which is risky. One multi-source BFS is about 4 × 10⁴.

3Intuition: ask your neighbours

The teacher's picture: a 1 asks each of its neighbours "how far is your nearest 0?". If a neighbour says "1", then this cell is 1 + 1 = 2 away, since it's one step further. If a neighbour says "2", it would be 1 + 2 = 3.

So every cell's answer = 1 + (the smallest answer among its neighbours). The hard part is filling cells in the right order so that neighbours already know their answers. BFS from all the 0s gives exactly that order: the 0s first, then cells at distance 1, then 2…

Her 3-question checklist before coding:

4Building the logic from her examples

Why only 4 directions? Read it from the output

In Example 2, the bottom-middle 1 has 0s diagonally above it, at (1,0) and (1,2). If diagonals were allowed, its answer would be 1. The expected output says 2. So diagonal moves are not allowed. The teacher's general rule: if a question allows diagonals, it says so.

Why not DFS?

  0  1  1          the circled cell has two routes to a 0:
  1  1  1          up: through (0,1)   → 1 + 1 = 2
  1  0  1          down: (2,1) is 0   → 0 + 1 = 1  ← the real answer

With DFS, a cell would follow one neighbour deep down and take whatever that path reports. If it happens to go up first, it gets 2 and may lock that in, while a better route existed. To be correct, DFS would have to explore every route and take the minimum, which is slow. BFS doesn't have this problem: all routes grow at the same speed, one layer at a time, so the shortest one always arrives first. Once a cell is marked, a later (longer) route won't overwrite it.

Why is this multi-source?

Two clues from the teacher: (1) the question doesn't name a start cell, and (2) it wants an answer for every cell, measured to the nearest 0. Distances are counted from 0s, so the 0s are where the ripples begin, and there are many of them. So push every 0 into the queue before the loop starts, each with distance 0. (See Part 0 for why they must all start together.)

Setting up the distance grid

We don't change the input grid (her habit: only modify the input if the interviewer agrees). We make dist, the same size:

• A 0-cell: dist = 0 (you're standing on a 0, no travel needed). It's also pushed into the queue.
• A 1-cell: dist = −1. This is just a "not filled yet" marker. The real value gets written later from its parent, so the starting number doesn't matter as long as it's different from every real distance.

The rule for stepping into a neighbour

Pop (r, c). For each of the 4 directions, go to (nr, nc) only if:

1. it's inside the grid, and
2. dist[nr][nc] == -1 (not visited yet).

Then set dist[nr][nc] = dist[r][c] + 1 and push it.

5Approach steps

1. Make dist (m×n) and an empty queue.
2. For every cell: if it's 0 → dist = 0 and push it. Else → dist = −1.
3. While the queue isn't empty: pop (r, c).
4. For each of the 4 directions: if the neighbour is inside and its dist is −1 → set it to dist[r][c] + 1 and push it.
5. Return dist.

6Code (Python)

from collections import deque

class Solution:
    def updateMatrix(self, mat):
        m, n = len(mat), len(mat[0])
        dist = [[-1] * n for _ in range(m)]
        queue = deque()

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0          # standing on a 0
                    queue.append((i, j))    # every 0 is a source

        directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1   # one step further than the parent
                    queue.append((nr, nc))
        return dist

7Code line by line

8Dry run (her Example 2)

mat              index map
0 0 0            (0,0) (0,1) (0,2)
0 1 0            (1,0) (1,1) (1,2)
1 1 1            (2,0) (2,1) (2,2)

Setup: the 0s are (0,0), (0,1), (0,2), (1,0), (1,2). All get dist 0 and go into the queue in that order. The 1s get −1.

 0  0  0
 0 -1  0
-1 -1 -1

 0  0  0
 0  1  0
 1 -1  1

 0  0  0
 0  1  0
 1  2  1

Look at step 4: when (1,0) is popped, (1,1) is already 1, so it's skipped. That's the "mark when you push" rule doing its job. And (2,1) gets 2 because the first cell to reach it was (1,1), which is at distance 1. A longer route would arrive later and find it already filled.

9Complexity & remember

• Time O(4 · m · n) = O(m·n): each cell enters the queue once and tries 4 directions. (In the video she writes this as "4 + m×n". She means 4 times m×n. Either way, it's linear in the number of cells.)
• Space O(m·n): the queue can hold every cell once, and dist is m×n. A separate visited grid would add another m×n, and the −1 trick avoids it.
• If the interviewer asks to cut the dist grid too, that's the hint to write the distances into mat itself.

Part B · Revision page

s = Solution()
print(s.updateMatrix([[0, 0, 0], [0, 1, 0], [0, 0, 0]]))   # [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
print(s.updateMatrix([[0, 0, 0], [0, 1, 0], [1, 1, 1]]))   # [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
print(s.updateMatrix([[0]]))                               # [[0]]
print(s.updateMatrix([[1, 1, 1], [1, 1, 1], [1, 1, 0]]))   # [[4, 3, 2], [3, 2, 1], [2, 1, 0]]
print(s.updateMatrix([[0, 1, 1, 1, 1, 0]]))                # [[0, 1, 2, 2, 1, 0]]

Based on this video: 01 Matrix | Multi-source BFS