NeetCode #619LC-773HardGraphs
← Back to All Problems#619 · #773 · Sliding Puzzle(滑动谜题)
📌 Problem Statement & Constraints
On a 2x3 board there are tiles 1-5 and a blank (0). A move slides a tile into the adjacent blank. Given a board configuration, return the minimum moves to reach
[[1,2,3],[4,5,0]], or -1. Constraints: board.length == 2, board[i].length == 3, the board is a permutation of 0..5.💡 Core Algorithmic Approaches
- BFS over board states, encoded as a 6-character string for hashing.
- The blank's legal moves depend on its position: index 0 can swap with 1 and 3, index 1 with 0, 2 and 4, and so on.
- A precomputed move table makes each expansion O(1).
- There are only
6! = 720states, so the BFS is trivially fast.
💻 Benchmark Python3 Implementation
class Solution:
def slidingPuzzle(self, board: List[List[int]]) -> int:
from collections import deque
start = "".join(str(x) for row in board for x in row)
target = "123450"
# adjacent indices for each blank position on a 2x3 board
moves = {0: (1, 3), 1: (0, 2, 4), 2: (1, 5),
3: (0, 4), 4: (1, 3, 5), 5: (2, 4)}
q = deque([(start, 0)])
seen = {start}
while q:
state, d = q.popleft()
if state == target:
return d
i = state.index("0") # the blank's position
for j in moves[i]:
lst = list(state)
lst[i], lst[j] = lst[j], lst[i] # slide a tile in
nxt = "".join(lst)
if nxt not in seen:
seen.add(nxt)
q.append((nxt, d + 1))
return -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(6! * 3) = O(1): at most 720 states with at most 3 moves each.
💾 Space Complexity
O(6!) for the visited set.
⚠️ Interview Pitfalls & Follow-ups
- Getting the adjacency table wrong: the 2x3 layout wraps differently from a 1x6 row.
- Swapping in place on the string: strings are immutable, so a list round-trip is needed.
- Using A\* or a heuristic: unnecessary at 720 states; BFS is exact and simple.
- Forgetting the blank's index lookup:
state.index("0")is O(6) and fine here.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.