A 2 × 3 board holds tiles 1–5 and an empty square 0. A move swaps 0 with an adjacent tile. Return the fewest moves to reach [[1, 2, 3], [4, 5, 0]], or -1 if impossible.
Before you code
Each board is a vertex and each move an edge. There are only 6!/2 = 360 reachable boards from any start, so BFS is enough; A* with a good heuristic explores fewer.
Hints
- Encode boards as strings such as "123450", with a precomputed neighbor list for each position of 0.
- BFS from the start board; the first time you reach the goal, return the depth.
- A* version: h = sum of Manhattan distances of tiles 1–5 to their home squares, which never overestimates.
Production & complexity notes
When solving Sliding puzzle on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in A* and heuristics to reinforce the underlying pattern.
What it practices
Searching an implicit graph with a heuristic, from A* and heuristics.