Problem Breakdown
Maze Solver
Published ·
medium
Try This Problem Yourself
Practice in the AI-enabled editor with real-time feedback
You're given a 2D grid. Each cell is a wall (#), open (.), the start (S), the end (E), or a one-way passage (> or <). Return the shortest path from S to E as an ordered list of positions, or null / None if no path exists.
input: shortest path:
##### #####
#S..# #S**#
#.#.# → #.#*#
#..E# #..E#
##### #####S and E are the path's endpoints, and the three stars in between mark the interior cells the shortest route passes through. That's five cells on the path in total. Any path that reuses a cell is longer than the shortest, so visited bookkeeping matters.
Pattern: Graph Search & Pathfinding
Finding the shortest path through the grid is breadth-first search. Treat each open cell as a node, explore outward layer by layer, and the first time you reach the exit you've found the shortest route.
Solution 1, BFS with a list queue and a list visited set
Breadth-first search is the natural choice because the grid is unweighted, meaning every move between adjacent cells costs the same one step. BFS explores outward from S in concentric waves, starting with the cells reachable in one step, then the cells reachable in two, and so on, with each wave expanding only from what the previous wave newly discovered. The first wave that touches E must be the shortest, because a shorter route would have surfaced E on an earlier wave and no wave ever revisits a cell.
Complexity
Where it breaks
Solution 2, BFS with a constant-time queue and a hash set
Complexity
Where it lands
One-way passages
Benchmarks
Takeaways
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium