Builds on Level-Order BFS and Graph BFS, which you haven’t finished yet.
Shortest Path BFS (Unweighted Grid / Graph)
dist, the number of moves from the start, which is the fewest because BFS reaches nodes in order of distance.You're given an n x n binary grid. Starting at corner cell (0, 0) and finishing at the opposite corner (n - 1, n - 1), find the shortest clear path between them, or report -1 if no such path exists.
A path counts as clear when every cell it visits holds 0, and each consecutive pair of cells touches 8-directionally — sharing a side or merely a corner both count as touching.
A clear path's length is simply how many cells it visits, start to finish.
(0,0) to (1,1): the path visits 2 cells.Shortest-Path BFS
start cell (0, 0) âž” 8/4-way delta scan âž” target hit (N-1, N-1)| 1 | from collections import deque |
| 2 | from typing import Callable, Hashable, Iterable, List |
| 3 | Â |
| 4 | Â |
| 5 | def fewest_steps(start: Hashable, is_goal: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Hashable]]) -> int: |
| 6 | """Shortest-Path BFS: the fewest moves from start to a cell where is_goal holds, or -1. |
| 7 | neighbors(cell) lists the cells one move away that may be entered. |
| 8 | Precondition: every move costs one step. |
| 9 | V = the cells reached. T = the cost of one is_goal or neighbors call (it lists at most T cells). |
| 10 | Time: O(V * T) | Space: O(V) queue and seen |
| 11 | """ |
| 12 | queue = deque([(start, 0)]) # (cell, moves taken to reach it) |
| 13 | seen = {start} # cells already queued, so each one is enqueued once |
| 14 | Â |
| 15 | while queue: |
| 16 | # 1. Pop and Check for the Goal: |
| 17 | # Every move costs exactly 1, so the first time is_goal is true, dist is the |
| 18 | # shortest distance from start — no later pop can report less. |
| 19 | cell, dist = queue.popleft() |
| 20 | if is_goal(cell): |
| 21 | return dist |
| 22 | Â |
| 23 | # 2. Enqueue Every Unseen Neighbour: |
| 24 | # Marking a neighbour seen at enqueue time, not at pop time, stops it from |
| 25 | # being queued twice while it is still waiting in line. |
| 26 | for nxt in neighbors(cell): |
| 27 | if nxt not in seen: |
| 28 | seen.add(nxt) |
| 29 | queue.append((nxt, dist + 1)) |
| 30 | Â |
| 31 | return -1 |
queue in non-decreasing order of dist, and a cell is marked 1 the moment it is first reached, which is by a shortest path.Treat each cell as a node and each allowed move (4 or 8 directions) as an edge of cost 1. BFS reaches cells in order of distance, so the first time you pop the target, its distance is the shortest. Store the distance together with the cell in the queue. The trap is marking too late: set grid[nr][nc] = 1 when you add a cell to the queue, not when you pop it, or the same cell is queued again and again by its neighbours.
See it run
Shortest-Path BFS, step by step
dist -queue (0, 0):1
Each cell of the grid is one cell of the board. # is a wall. A number is the dist the cell was pushed with. A blank cell has not been reached.
popthe cell taken from the front of the queuepusheda clear cell that is marked and pushed nowseena neighbour that is already marked, so it is skipped
Start: grid[0][0] is clear. It is marked and pushed with dist = 1, because the path counts cells.
Gotcha 1 of 5
- The trap
Gotcha 1: Marking a cell when it is popped, not when pushed
Mistaker, c, dist = queue.popleft() grid[r][c] = 1 ... queue.append((nr, nc, dist + 1))Fixr, c, dist = queue.popleft() ... grid[nr][nc] = 1 queue.append((nr, nc, dist + 1))What happens: A cell that is queued but not yet popped still reads
0ingrid. Each of its neighbours that is popped meanwhile pushes it again. So the same cell can sit in the queue many times. The answer is still right, but the queue and the work grow many times over.
- Edges have different weights, as in Network Delay Time (LC 743), so the path with the fewest steps is not always the cheapest. See Dijkstra
- Where you are is a whole lock code, word or board, not a cell, as in Open the Lock (LC 752), and the neighbours of a state must be generated rather than read from a grid. See State-Space BFS
Deep Dive
Why the first arrival at a cell is the shortest path to it
Graph BFS (visit-once) already marks a cell when it is pushed, so each cell enters queue once. This card adds one number to each entry: dist, the number of cells on the path from the start. The question is why that first dist is also the smallest.
Every move costs one step. Pop a cell with dist = d. Each cell it pushes gets dist = d + 1 and goes to the back of queue. So queue holds cells with dist equal to d, then cells with dist equal to d + 1, and the pops come out in non-decreasing order of dist.
A cell is first reached from the first popped cell that lists it. Every cell with a smaller dist was popped earlier and did not list it. So no shorter path exists, and the stored dist is final. The first time the bottom-right cell is popped, its dist is the answer.
Example: in Shortest Path in Binary Matrix (LC 1091), the grid [[0,0,0],[1,1,0],[1,1,0]] pops (0, 0) with dist = 1, then (0, 1) with 2, then (0, 2) and (1, 2) with 3, then (2, 2) with 4. The answer is 4.
One trace: a later sighting never lowers dist
The board replays the grid from the previous section. A # is a wall. A number is the dist a cell was pushed with.
Pop (0, 1) with dist = 2. It pushes (0, 2) and (1, 2), and both get dist = 3.
Now pop (0, 2). Its neighbour (1, 2) is clear, but it already has dist = 3, so the loop skips it. This is the step marked as the trap on the board.
Skipping is correct. (0, 2) has dist = 3, so a path to (1, 2) through it would have dist = 4. That is larger than the 3 already stored. A later sighting never gives a smaller value, so do not overwrite it.
The cost: cells times work per cell
The card's complexity line is O(V * T). V is the number of cells that are reached. T is the work to list the neighbours of one cell and test one of them.
In shortestPathBinaryMatrix, the grid has N * N cells. Each cell is pushed at most once, as in Graph BFS. Each pop checks 8 neighbours, and every check is O(1). So T is a constant, and the total is O(N^2) time.
queue and the marks in grid hold at most one entry per cell, so the space is O(N^2). The blueprint marks the cells inside grid, which adds no extra set.
Example: an empty 3 by 3 grid pushes 9 cells, and an empty 6 by 6 grid pushes 36. The count follows N * N, as the formula says.
What dist counts, and which problems fit
The generic template fewest_steps starts with dist = 0 and counts moves. Shortest Path in Binary Matrix (LC 1091) counts the cells on the path, and the start cell is on the path. So the blueprint starts with dist = 1. Read how each problem measures length before you choose the start value.
Example: for [[0,1],[1,0]], the path is (0, 0) then (1, 1). That is 2 cells and 1 move. The right answer is 2, and starting with dist = 0 returns 1.
The loop never tests the start cell, because the start is pushed before the loop. The guard grid[0][0] != 0 must therefore run first. For [[1,0],[0,0]] the right answer is -1, and a search without that guard returns 2.
The same template fits any graph where every move costs the same. Jump Game IV (LC 1345) lists the neighbours of index i as i - 1, i + 1, and every index with the same value. Only the neighbors function changes.
If the moves cost different amounts, as in Network Delay Time (LC 743), the first pop of the goal is not always the cheapest path. Use a cheapest-first search instead.
60-Second Pitch
"Every move costs one step, so I use BFS from the start cell. It is the usual graph BFS that marks a cell when it is pushed, and each entry in queue also carries its dist. BFS pops cells in non-decreasing order of dist. So the first time I pop the bottom-right cell, its dist is the shortest path, and no later pop can be smaller. Each cell is pushed once, and each pop checks 8 neighbours. That gives O(N^2) time and O(N^2) space for an N by N grid. I check the start and end cells first, because the loop never tests the start. If queue empties, I return -1."
Common Questions
- Why use BFS and not DFS to find the shortest path?
DFS follows one path to its end before it tries another. The first path it finds to the goal is not always the shortest, so it would have to try every path. BFS reaches cells in order of
dist, so the first time it reaches the goal, thatdistis the smallest.- Why is the first
distof a cell the smallest? Cells leave
queuein non-decreasing order ofdist. The first popped cell that lists a neighbour has the smallestdistof all cells that list it, so the neighbour gets thatdistplus 1. A later sighting can only give an equal or larger value, so it is skipped.- What are the time and space complexity?
O(N^2) time and O(N^2) space for an N by N grid. Each cell is pushed once, and each pop looks at 8 neighbours in constant time. In the generic template it is O(V * T), where
Vis the number of reached cells andTis the cost of oneneighborscall.- How do you return the path and not only its length?
Store a
parentfor each cell when you push it, which is the cell that was popped at that time. When the goal is popped, followparentback to the start and reverse the list. Each cell has one parent because it is pushed only once.- What changes when the moves have different costs?
The first pop of the goal is then not always the cheapest, because a path with more steps can cost less. If the costs are only 0 and 1, a deque (double-ended queue) can keep the order. For general positive costs, use a cheapest-first search with a heap, as in Network Delay Time (LC 743).
SWE Reasoning
Spot it
- The question asks for the fewest moves, steps or jumps from one start to one target.
- Every move costs the same: one step in a grid, one jump, one knight move.
- The state of the search is a position that a grid or a list of neighbours already describes. Nothing else changes between visits.
- A DFS (depth-first search) would find some path, but you would have to try every path to prove which one is shortest.
- The statement says to return -1 when the target cannot be reached. BFS ends with an empty
queuein that case.
The invariant, step by step
- The guard checks that
grid[0][0]andgrid[n - 1][n - 1]are clear. Thenqueueholds(0, 0, 1), andgrid[0][0]is set to 1. - The loop pops the front of
queue. If it is the bottom-right cell, it returnsdist. - For each of the 8 directions, a neighbour that is inside the grid and equal to 0 is marked as 1 and pushed with
dist + 1. This is the mark on push of Graph BFS (visit-once). - A marked cell is never pushed again, so its first
distis never replaced. - The pushed cells go to the back, so
queueholds cells withdistequal todand thend + 1. The pops come out in non-decreasing order ofdist. - The first pop of the bottom-right cell therefore has the smallest possible
dist. Ifqueuebecomes empty first, the corner cannot be reached, and the function returns -1.
Traps
- Marking at pop time. This is the trap of Graph BFS (visit-once). Here it also means a cell can be pushed twice with different
distvalues. Setgrid[nr][nc] = 1when you push. - Missing start check. The loop never tests
grid[0][0]. For[[1,0],[0,0]]the search returns 2 instead of -1. Check both corners before the loop. - Wrong start value. In Shortest Path in Binary Matrix (LC 1091), the start cell counts, so
diststarts at 1. For[[0,1],[1,0]], starting at 0 returns 1 instead of 2. - Mutating the caller's grid. The search writes 1 into
grid. Code that readsgridafter the call sees the visited cells as walls. Pass[row[:] for row in grid]when the grid is needed again. - Same-value scans in Jump Game IV (LC 1345). An index can jump to every index with its value. If the list of those indices is not cleared after it is used, every later index with that value scans it again, and the time becomes O(n^2).
Practice
Builds on Level-Order BFS and Graph BFS, which you haven’t finished yet.
Shortest Path BFS (Unweighted Grid / Graph)
dist, the number of moves from the start, which is the fewest because BFS reaches nodes in order of distance.You're given an n x n binary grid. Starting at corner cell (0, 0) and finishing at the opposite corner (n - 1, n - 1), find the shortest clear path between them, or report -1 if no such path exists.
A path counts as clear when every cell it visits holds 0, and each consecutive pair of cells touches 8-directionally — sharing a side or merely a corner both count as touching.
A clear path's length is simply how many cells it visits, start to finish.
(0,0) to (1,1): the path visits 2 cells.Shortest-Path BFS
start cell (0, 0) âž” 8/4-way delta scan âž” target hit (N-1, N-1)| 1 | from collections import deque |
| 2 | from typing import Callable, Hashable, Iterable, List |
| 3 | Â |
| 4 | Â |
| 5 | def fewest_steps(start: Hashable, is_goal: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Hashable]]) -> int: |
| 6 | """Shortest-Path BFS: the fewest moves from start to a cell where is_goal holds, or -1. |
| 7 | neighbors(cell) lists the cells one move away that may be entered. |
| 8 | Precondition: every move costs one step. |
| 9 | V = the cells reached. T = the cost of one is_goal or neighbors call (it lists at most T cells). |
| 10 | Time: O(V * T) | Space: O(V) queue and seen |
| 11 | """ |
| 12 | queue = deque([(start, 0)]) # (cell, moves taken to reach it) |
| 13 | seen = {start} # cells already queued, so each one is enqueued once |
| 14 | Â |
| 15 | while queue: |
| 16 | # 1. Pop and Check for the Goal: |
| 17 | # Every move costs exactly 1, so the first time is_goal is true, dist is the |
| 18 | # shortest distance from start — no later pop can report less. |
| 19 | cell, dist = queue.popleft() |
| 20 | if is_goal(cell): |
| 21 | return dist |
| 22 | Â |
| 23 | # 2. Enqueue Every Unseen Neighbour: |
| 24 | # Marking a neighbour seen at enqueue time, not at pop time, stops it from |
| 25 | # being queued twice while it is still waiting in line. |
| 26 | for nxt in neighbors(cell): |
| 27 | if nxt not in seen: |
| 28 | seen.add(nxt) |
| 29 | queue.append((nxt, dist + 1)) |
| 30 | Â |
| 31 | return -1 |
queue in non-decreasing order of dist, and a cell is marked 1 the moment it is first reached, which is by a shortest path.Treat each cell as a node and each allowed move (4 or 8 directions) as an edge of cost 1. BFS reaches cells in order of distance, so the first time you pop the target, its distance is the shortest. Store the distance together with the cell in the queue. The trap is marking too late: set grid[nr][nc] = 1 when you add a cell to the queue, not when you pop it, or the same cell is queued again and again by its neighbours.
See it run
Shortest-Path BFS, step by step
dist -queue (0, 0):1
Each cell of the grid is one cell of the board. # is a wall. A number is the dist the cell was pushed with. A blank cell has not been reached.
popthe cell taken from the front of the queuepusheda clear cell that is marked and pushed nowseena neighbour that is already marked, so it is skipped
Start: grid[0][0] is clear. It is marked and pushed with dist = 1, because the path counts cells.
Gotcha 1 of 5
- The trap
Gotcha 1: Marking a cell when it is popped, not when pushed
Mistaker, c, dist = queue.popleft() grid[r][c] = 1 ... queue.append((nr, nc, dist + 1))Fixr, c, dist = queue.popleft() ... grid[nr][nc] = 1 queue.append((nr, nc, dist + 1))What happens: A cell that is queued but not yet popped still reads
0ingrid. Each of its neighbours that is popped meanwhile pushes it again. So the same cell can sit in the queue many times. The answer is still right, but the queue and the work grow many times over.
- Edges have different weights, as in Network Delay Time (LC 743), so the path with the fewest steps is not always the cheapest. See Dijkstra
- Where you are is a whole lock code, word or board, not a cell, as in Open the Lock (LC 752), and the neighbours of a state must be generated rather than read from a grid. See State-Space BFS
Deep Dive
Why the first arrival at a cell is the shortest path to it
Graph BFS (visit-once) already marks a cell when it is pushed, so each cell enters queue once. This card adds one number to each entry: dist, the number of cells on the path from the start. The question is why that first dist is also the smallest.
Every move costs one step. Pop a cell with dist = d. Each cell it pushes gets dist = d + 1 and goes to the back of queue. So queue holds cells with dist equal to d, then cells with dist equal to d + 1, and the pops come out in non-decreasing order of dist.
A cell is first reached from the first popped cell that lists it. Every cell with a smaller dist was popped earlier and did not list it. So no shorter path exists, and the stored dist is final. The first time the bottom-right cell is popped, its dist is the answer.
Example: in Shortest Path in Binary Matrix (LC 1091), the grid [[0,0,0],[1,1,0],[1,1,0]] pops (0, 0) with dist = 1, then (0, 1) with 2, then (0, 2) and (1, 2) with 3, then (2, 2) with 4. The answer is 4.
One trace: a later sighting never lowers dist
The board replays the grid from the previous section. A # is a wall. A number is the dist a cell was pushed with.
Pop (0, 1) with dist = 2. It pushes (0, 2) and (1, 2), and both get dist = 3.
Now pop (0, 2). Its neighbour (1, 2) is clear, but it already has dist = 3, so the loop skips it. This is the step marked as the trap on the board.
Skipping is correct. (0, 2) has dist = 3, so a path to (1, 2) through it would have dist = 4. That is larger than the 3 already stored. A later sighting never gives a smaller value, so do not overwrite it.
The cost: cells times work per cell
The card's complexity line is O(V * T). V is the number of cells that are reached. T is the work to list the neighbours of one cell and test one of them.
In shortestPathBinaryMatrix, the grid has N * N cells. Each cell is pushed at most once, as in Graph BFS. Each pop checks 8 neighbours, and every check is O(1). So T is a constant, and the total is O(N^2) time.
queue and the marks in grid hold at most one entry per cell, so the space is O(N^2). The blueprint marks the cells inside grid, which adds no extra set.
Example: an empty 3 by 3 grid pushes 9 cells, and an empty 6 by 6 grid pushes 36. The count follows N * N, as the formula says.
What dist counts, and which problems fit
The generic template fewest_steps starts with dist = 0 and counts moves. Shortest Path in Binary Matrix (LC 1091) counts the cells on the path, and the start cell is on the path. So the blueprint starts with dist = 1. Read how each problem measures length before you choose the start value.
Example: for [[0,1],[1,0]], the path is (0, 0) then (1, 1). That is 2 cells and 1 move. The right answer is 2, and starting with dist = 0 returns 1.
The loop never tests the start cell, because the start is pushed before the loop. The guard grid[0][0] != 0 must therefore run first. For [[1,0],[0,0]] the right answer is -1, and a search without that guard returns 2.
The same template fits any graph where every move costs the same. Jump Game IV (LC 1345) lists the neighbours of index i as i - 1, i + 1, and every index with the same value. Only the neighbors function changes.
If the moves cost different amounts, as in Network Delay Time (LC 743), the first pop of the goal is not always the cheapest path. Use a cheapest-first search instead.
60-Second Pitch
"Every move costs one step, so I use BFS from the start cell. It is the usual graph BFS that marks a cell when it is pushed, and each entry in queue also carries its dist. BFS pops cells in non-decreasing order of dist. So the first time I pop the bottom-right cell, its dist is the shortest path, and no later pop can be smaller. Each cell is pushed once, and each pop checks 8 neighbours. That gives O(N^2) time and O(N^2) space for an N by N grid. I check the start and end cells first, because the loop never tests the start. If queue empties, I return -1."
Common Questions
- Why use BFS and not DFS to find the shortest path?
DFS follows one path to its end before it tries another. The first path it finds to the goal is not always the shortest, so it would have to try every path. BFS reaches cells in order of
dist, so the first time it reaches the goal, thatdistis the smallest.- Why is the first
distof a cell the smallest? Cells leave
queuein non-decreasing order ofdist. The first popped cell that lists a neighbour has the smallestdistof all cells that list it, so the neighbour gets thatdistplus 1. A later sighting can only give an equal or larger value, so it is skipped.- What are the time and space complexity?
O(N^2) time and O(N^2) space for an N by N grid. Each cell is pushed once, and each pop looks at 8 neighbours in constant time. In the generic template it is O(V * T), where
Vis the number of reached cells andTis the cost of oneneighborscall.- How do you return the path and not only its length?
Store a
parentfor each cell when you push it, which is the cell that was popped at that time. When the goal is popped, followparentback to the start and reverse the list. Each cell has one parent because it is pushed only once.- What changes when the moves have different costs?
The first pop of the goal is then not always the cheapest, because a path with more steps can cost less. If the costs are only 0 and 1, a deque (double-ended queue) can keep the order. For general positive costs, use a cheapest-first search with a heap, as in Network Delay Time (LC 743).
SWE Reasoning
Spot it
- The question asks for the fewest moves, steps or jumps from one start to one target.
- Every move costs the same: one step in a grid, one jump, one knight move.
- The state of the search is a position that a grid or a list of neighbours already describes. Nothing else changes between visits.
- A DFS (depth-first search) would find some path, but you would have to try every path to prove which one is shortest.
- The statement says to return -1 when the target cannot be reached. BFS ends with an empty
queuein that case.
The invariant, step by step
- The guard checks that
grid[0][0]andgrid[n - 1][n - 1]are clear. Thenqueueholds(0, 0, 1), andgrid[0][0]is set to 1. - The loop pops the front of
queue. If it is the bottom-right cell, it returnsdist. - For each of the 8 directions, a neighbour that is inside the grid and equal to 0 is marked as 1 and pushed with
dist + 1. This is the mark on push of Graph BFS (visit-once). - A marked cell is never pushed again, so its first
distis never replaced. - The pushed cells go to the back, so
queueholds cells withdistequal todand thend + 1. The pops come out in non-decreasing order ofdist. - The first pop of the bottom-right cell therefore has the smallest possible
dist. Ifqueuebecomes empty first, the corner cannot be reached, and the function returns -1.
Traps
- Marking at pop time. This is the trap of Graph BFS (visit-once). Here it also means a cell can be pushed twice with different
distvalues. Setgrid[nr][nc] = 1when you push. - Missing start check. The loop never tests
grid[0][0]. For[[1,0],[0,0]]the search returns 2 instead of -1. Check both corners before the loop. - Wrong start value. In Shortest Path in Binary Matrix (LC 1091), the start cell counts, so
diststarts at 1. For[[0,1],[1,0]], starting at 0 returns 1 instead of 2. - Mutating the caller's grid. The search writes 1 into
grid. Code that readsgridafter the call sees the visited cells as walls. Pass[row[:] for row in grid]when the grid is needed again. - Same-value scans in Jump Game IV (LC 1345). An index can jump to every index with its value. If the list of those indices is not cleared after it is used, every later index with that value scans it again, and the time becomes O(n^2).