DSA sheet · Graphs · BFS shortest path pattern

Shortest Path in Binary Matrix

This is the first "shortest path" problem of the graph pattern. The grid is a graph, every step costs the same, and the teacher shows why that one fact means plain BFS already gives the shortest path, with no fancy algorithm needed. She also shows a neat space saving: the distance grid doubles as the visited grid, so we never build a separate visited array. She says it's very close to 01 Matrix (in her playlist she recorded 01 Matrix just before this one). The big difference is that here there is one starting cell, not many.

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
• Part A · BFS with a distance grid (single source, 8 directions)
• Part B · Revision page

Part 0 · Before starting

Nodes and edges

A graph is a set of nodes (points, also called vertices) joined by edges (lines). An edge says "you can go directly from this node to that one".

(0)—(1)—(2)
 |       |
(3)—————(4)

• Undirected edge (0)—(1): you can walk both ways. Directed edge (0)→(1): only from 0 to 1.
• Weighted edge (0)—5—(1): walking it costs 5. Unweighted: every edge costs the same, so we just count edges (each costs 1). This problem is unweighted, and that is the reason BFS works.

Reading a graph and building an adjacency list

Normal graph problems give an edge list like [[0,1],[1,2]] or an adjacency matrix (an n×n table where m[u][v] = 1 means an edge). We usually turn it into an adjacency list: for every node, the list of its neighbours. It answers "where can I go from here?" quickly.

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

Grids are graphs too, and need no adjacency list

In a grid, each cell (r, c) is a node. Its neighbours are the cells around it. The teacher's point: we build an adjacency list only when we don't know who the neighbours are. In a grid we always know: just add small offsets to the row and column. So a grid needs no adjacency list; a small list of directions is enough.

  4 directions (this problem uses 8)      8 directions
                (r-1,c)                 (r-1,c-1) (r-1,c) (r-1,c+1)
                   ↑                         ↖      ↑      ↗
       (r,c-1) ← (r,c) → (r,c+1)    (r,c-1) ←   (r,c)   → (r,c+1)
                   ↓                         ↙      ↓      ↘
                (r+1,c)                 (r+1,c-1) (r+1,c) (r+1,c+1)

• Bounds check: a neighbour like (-1, 0) is outside the grid. Before touching a cell, check 0 <= nr < rows and 0 <= nc < cols.
• Diagonals only when the question says so. The teacher repeats this in every grid problem: if moving diagonally were allowed, the question would say it. Here it does say "8-directionally", so we use all 8.

Visited: why we need it

In a graph you can walk in circles: A → B → A → B… If we don't remember which nodes we already reached, BFS keeps adding them again and never stops. A visited set/array marks "already reached, don't add again". Usually it's a separate array. In this problem we'll get it for free from the distance grid (Part A, step 4).

A connected component is a group of nodes that can all reach each other. If the start and the target are in different components (a wall of 1s separates them), there is no path, and the answer is −1.

BFS (breadth first search): level by level with a queue

BFS starts at one node and visits it, then all nodes 1 step away, then all nodes 2 steps away, and so on. It uses a queue (collections.deque): add at the back with append, remove from the front with popleft. Rule: mark a node visited when you push it, so it can never be pushed twice.

from collections import deque

adj = [[1, 3], [0, 2], [1, 4], [0, 4], [3, 2]]
dist = [-1] * len(adj)           # -1 means "not reached yet" (also our visited mark)
dist[0] = 0
queue = deque([0])
while queue:
    u = queue.popleft()
    for v in adj[u]:
        if dist[v] == -1:        # not visited
            dist[v] = dist[u] + 1
            queue.append(v)
print(dist)   # [0, 1, 2, 1, 2]

DFS (depth first search) instead runs down one path as far as possible (recursion or a stack), then backs up. Good for "reach everything" questions, but it does not find shortest paths, as we'll see.

Why BFS layers give the shortest path (unweighted graphs)

Think of dropping a stone in still water. The ripple reaches everything 1 step away first, then 2 steps, then 3. BFS is that ripple.

layer 1:  S                      the queue always looks like
layer 2:  every cell 1 step from S        [ layer d ... | layer d+1 ... ]
layer 3:  every cell 2 steps from S       never a layer d+2 cell before a layer d+1 cell

1. The queue holds cells in non-decreasing distance order. We start with only S. Every time we pop a cell at distance d, we push its new neighbours at distance d+1 at the back. So all distance-d cells come out before any distance-(d+1) cell.
2. Suppose a cell X is first reached at distance d. Could there be a shorter path, say d−1? Then the cell just before X on that shorter path has distance d−2 and would have been popped earlier, and it would have pushed X with d−1. That didn't happen, so no shorter path exists.
3. So the first time BFS reaches a cell, its distance is the shortest. That's why we never update a visited cell again.

Part A · BFS with a distance grid

LeetCode 1091

1The question in simple words

You get an n×n grid of 0s and 1s. Find the length of the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). If there is no clear path, return −1.

A clear path means:

• Every cell on the path holds 0. Think of a 1 as a wall (blocked).
• You may move in 8 directions: up, down, left, right and the 4 diagonals. "Sharing an edge or a corner" just means one step to a touching cell. It does not mean sliding any distance along a diagonal.
• The length is the number of cells you visit, counting the start and the end. (Not the number of moves. A path with 2 cells has 1 move but length 2.)

 0  1
 1  0
 one diagonal step:
 cells (0,0),(1,1) = 2

 0  0  0
 1  1  0
 1  1  0
 (0,0)→(0,1)→(1,2)→(2,2)

 1  0  0
 1  1  0
 1  1  0
 start is a wall

The teacher also notes the type of problem: the question names the start cell, so this is a single-source shortest path. (In 01 Matrix no start was named, every 0 was a start, so that one was multi-source.)

2What the constraints tell us

• n == grid.length == grid[i].length → the grid is square: rows = cols = n. One variable is enough.
• 1 <= n <= 100 → at most 100 × 100 = 10⁴ cells. n can be 1 (a single cell), so the start may also be the end.
• Each cell is 0 or 1 → it's a "binary" matrix.
• Speed: we look at each cell once and try 8 directions from it, so about 8 × 10⁴ steps. That's tiny. The teacher's rough line: around 10⁸–10⁹ steps is where you start seeing TLE (Time Limit Exceeded). We are far below it.

3Intuition: a ripple from the top-left corner

Picture pouring water into the top-left cell. Each second it spreads into every touching 0-cell (8 ways), never into walls. The first second the water reaches the bottom-right cell is the length of the shortest path. Cells reached at the "same second" form one layer. That's exactly BFS.

Before coding, the teacher runs through her usual checklist of 3 questions for any graph problem:

4Building the logic from her examples

Base case first: blocked start or blocked end → −1

If grid[0][0] == 1, we can't even stand on the start. If grid[n-1][n-1] == 1, we can never finish on the end. Either way, no clear path exists.

Why do we need a distance grid?

The answer is a count of cells, so for every cell we need to remember "how many cells did it take to get here?". We make a separate grid dist of the same size, filled with 0.

The space trick: dist also tells us "visited"

The usual plan would be two extra grids: dist and visited. But look at what dist holds:

• The start gets distance 1 (it's one cell long already). Every other reached cell gets parent + 1, so 2, 3, 4…. Every reached cell has a positive distance.
• A cell never reached still has its starting value 0.

So dist[r][c] == 0 means "not visited" and dist[r][c] > 0 means "visited". We don't need a separate visited grid.

When can we step into a neighbour? Three checks

From a popped cell (r, c), for each of the 8 directions we compute nr, nc. We may go there only if all of these hold:

1. Inside the grid: 0 <= nr < n and 0 <= nc < n. In Example 2 from (0,0), going up or left falls off the grid.
2. Not a wall: grid[nr][nc] == 0. In Example 2, the cell below (0,0) is 1, so we can't go down.
3. Not visited: dist[nr][nc] == 0. From (0,1) we could step back to (0,0), but its distance is 1 (positive), so it's already visited. Skip it.

What do we do when we step in?

• dist[nr][nc] = dist[r][c] + 1: the child is one cell further than its parent. This also marks it visited.
• Push (nr, nc) into the queue, so later we explore its neighbours.

When do we stop? As soon as we POP the last cell

When the popped cell is (n-1, n-1), its distance was already written when it was pushed, and by the layer argument (Part 0) it is the smallest possible. So return dist[n-1][n-1] right away.

Why not DFS?

DFS dives down one path and reports the first route it finds to the end. That route can be long and winding. To get the shortest with DFS you'd have to try every path and keep the minimum, which is exponential. BFS reaches cells in order of distance, so its first arrival is the answer.

 0  0  0        DFS might go right, right, down, down = 5 cells
 0  0  0        BFS: (0,0) → (1,1) → (2,2) = 3 cells, found in layer 3
 0  0  0

5Approach steps

1. If the start or the end is 1 → return −1.
2. Make dist, an n×n grid of 0s. Set dist[0][0] = 1. Push (0, 0) into a queue.
3. Write the 8 direction pairs (dr, dc).
4. While the queue isn't empty: pop (r, c).
5. If (r, c) is the last cell → return dist[r][c].
6. For each of the 8 directions: if the new cell is inside, is 0 in grid, and is 0 in dist → set its distance to dist[r][c] + 1 and push it.
7. If the loop ends → return −1.

6Code (Python)

from collections import deque

class Solution:
    def shortestPathBinaryMatrix(self, grid):
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1

        dist = [[0] * n for _ in range(n)]     # 0 = not visited yet
        dist[0][0] = 1                         # the start cell counts as 1
        queue = deque([(0, 0)])

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1),       # up, down, left, right
                      (-1, -1), (-1, 1), (1, -1), (1, 1)]     # the 4 diagonals

        while queue:
            r, c = queue.popleft()
            if r == n - 1 and c == n - 1:      # reached the end: first arrival is shortest
                return dist[r][c]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n
                        and grid[nr][nc] == 0 and dist[nr][nc] == 0):
                    dist[nr][nc] = dist[r][c] + 1   # one more cell than the parent
                    queue.append((nr, nc))

        return -1                              # the end was never reached

7Code line by line

8Dry run (her Example 2)

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

 1  2  .
 #  #  .
 #  #  .

 1  2  3
 #  #  3
 #  #  .

 1  2  3
 #  #  3
 #  #  4

# = wall (grid value 1), . = not visited (dist 0). Notice (0,2) and (1,2) got their distance in the same step: they are the same layer, which is what the teacher means by "BFS goes to all children at the same time".

9Complexity & remember

• Time O(8 · n²) = O(n²): each cell enters the queue at most once (marked on push), so the while loop runs at most n² times, and each pop tries 8 directions. With n = 100 that's 8 × 10⁴, well under the TLE line.
• Space O(n²): the dist grid, plus the queue, which can hold up to about n² cells. We saved a whole extra n×n grid by not keeping a separate visited array.

Part B · Revision page

s = Solution()
print(s.shortestPathBinaryMatrix([[0, 1], [1, 0]]))                    # 2
print(s.shortestPathBinaryMatrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]))   # 4
print(s.shortestPathBinaryMatrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]]))   # -1
print(s.shortestPathBinaryMatrix([[0]]))                               # 1
print(s.shortestPathBinaryMatrix([[0, 0], [0, 1]]))                    # -1
print(s.shortestPathBinaryMatrix([[0, 1, 0], [1, 1, 0], [0, 0, 0]]))   # -1

Based on this video: Shortest Path in Binary Matrix | BFS