← DSA Atlas
Dedicated problem page · #505

The Maze II

MediumShortest Path, Dijkstra and Minimum Spanning TreeWeighted shortest path on a gridDijkstra where each roll is one weighted edge
Solve on LeetCode ↗
505
MediumShortest Path, Dijkstra and Minimum Spanning TreeDijkstra where each roll is one weighted edgeWeighted shortest path on a grid

The Maze II

A ball is in a maze of empty spaces (0) and walls (1). The ball can roll up, down, left, or right, but it does not stop rolling until it hits a wall. Given the maze, the ball's start position, and a destination, return the shortest distance (number of empty cells traveled) for the ball to stop at the destination, or -1 if it cannot stop there.

Open official problem prompt ↗
In plain English

Compute the fewest empty cells the ball must travel over to come to rest exactly on the destination.

Picture it like this

Like sliding a hockey puck on ice: once you push it, it glides until it slams into the boards; you pay for every tile it slides across.

Example
Input
maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output
12
Why
The shortest sequence of rolls that stops exactly at (4,4) covers 12 traveled cells.
Constraints
m == maze.length, n == maze[i].length1 <= m, n <= 100maze[i][j] is 0 or 1start and destination are empty cellsstart != destinationThe borders are all walls
Pattern lesson

See the pattern, then code

Weighted shortest path on a grid
Recognition clue

Each roll has a variable travel cost and we want the minimum total distance, so cells are nodes and rolls are weighted edges: Dijkstra.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Rolling collapses many cells into a single move whose weight is the number of cells crossed until a wall stops the ball. Minimizing total cells traveled is then a non-negative weighted shortest path.

New words, made simpleKnow these before the algorithm
Roll / slide
One move where the ball travels in a direction until blocked by a wall.
Edge weight
The number of empty cells crossed during a single roll.
Stopping cell
A cell adjacent to a wall in the roll direction where the ball comes to rest.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
BFS counting rolls

Wrong objective: it minimizes number of rolls, not total distance traveled.

Treat each roll as one step and BFS by number of rolls.

Time O(m*n*max(m,n))Space O(m*n)
Best choiceDijkstra on stopping cells

Correct because roll distances are non-negative and we minimize their sum.

Weight each roll by cells crossed and use a min-heap on total distance.

Time O(m*n*max(m,n)*log(m*n))Space O(m*n)
The rule we keep true

Invariant

dist[r][c] always holds the smallest known total travel distance to stop at cell (r, c); the value is final once (r, c) is popped from the heap.

Why this is correct

Reasoning

All roll weights are non-negative, so Dijkstra's greedy settle order is valid. Because the ball only stops next to walls, stopping cells are well-defined nodes and every path is a sequence of these weighted rolls.

The algorithm in three movesSay these aloud before coding
1Treat each stopping cell as a node; roll in all four directions until a wall stops the ball

dist[0][4]=0, push (0,0,4)

2Use a min-heap keyed by accumulated distance

roll and accumulate cells crossed per move

3Relax a stop position only when a shorter total distance reaches it

destination popped with d=12 -> return 12

4Return the distance when the destination is first popped, else -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
S(0,4)0
roll1
stop2
D(4,4)3
1 · Readstart (0,4)
2 · AskWhere can the ball rest first?
3 · Update statedist[0][4]=0, pq=[(0,0,4)]
4 · ResultPop start, roll in 4 directions
Key takeaway

Ball rolls until walls stop it; edge weight is cells crossed per roll.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Distance grid and heap

    Track best distance to each cell and seed the heap with the start.

  2. 2
    Lines 8-12Pop and validate

    Return early on destination; skip stale heap entries whose distance is outdated.

  3. 3
    Lines 13-18Simulate a roll

    Slide until the next cell is a wall or out of bounds, counting crossed cells.

  4. 4
    Lines 19-21Relax the stop

    Update and push the stopping cell only if this roll gives a shorter total distance.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Destination reachable by rolling through it but never stopping there -> that path is invalid, keep searching
  • Start adjacent to destination but ball rolls past it
  • Long open corridors making single rolls expensive
  • Destination unreachable -> return -1
!

Common beginner mistakes

  • Counting rolls instead of cells traveled solves the wrong problem (that is the simpler Maze BFS)
  • Allowing the destination to count when the ball only passes over it without stopping
  • Forgetting the stale-entry check leads to redundant expansions
Check your understanding

Why is plain BFS insufficient here even though the grid is unweighted-looking?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)#1135Connecting Cities With Minimum CostMinimum spanning tree (Kruskal)