TechPrep
Linked structures, trees and graphsReadLabPracticeCheck

Breadth-first search

Explore in rings of equal distance with a queue; the first time you reach a node is by a shortest path.

Shortest Path in a Grid. grid[r][c] is 0 for open and 1 for wall. Moving up, down, left or right, return the fewest steps from the top-left to the bottom-right, or -1 if impossible.

Signals that point here

The idea

A queue processes nodes in order of distance: all distance-d nodes leave before any distance-d + 1 node. So the first time the target is dequeued, its distance is minimal.

Mark a cell as seen when you enqueue it, not when you dequeue it. Otherwise the same cell enters the queue several times and the search can blow up from linear to quadratic.

from collections import deque

def shortest_path(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] or grid[rows - 1][cols - 1]:
        return -1
    queue = deque([(0, 0, 0)])           # row, col, distance
    seen = {(0, 0)}
    while queue:
        r, c, d = queue.popleft()
        if (r, c) == (rows - 1, cols - 1):
            return d
        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 not grid[nr][nc] and (nr, nc) not in seen:
                seen.add((nr, nc))       # mark on enqueue
                queue.append((nr, nc, d + 1))
    return -1

Complexity

O(R·C) time and space: each cell is enqueued at most once and has four neighbours.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: shortest_path([[0, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0], [0, 1, 1, 0]])

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the minutes until every orange is rotten, or -1.
  2. Return the level-order traversal of a binary tree as a list of lists.
  3. Find the length of the shortest transformation sequence between two words.

Check yourself

Why is the first dequeue of the target a shortest path?

The queue releases nodes in non-decreasing distance order.

When must you mark a node as seen?

When it is enqueued.

Saved in this browser.