NeetCode #614LC-499HardGraphsNC Algo100
← Back to All Problems#614 · #499 · The Maze III(迷宫 III)
📌 Problem Statement & Constraints
A ball rolls in a maze with
0 (empty), 1 (wall) and one hole. The ball falls into the hole if it passes over it. Given ball and hole, return the shortest instruction string using u, d, l, r, or impossible. Ties are broken by lexicographic order. Constraints: 1 <= m, n <= 100.💡 Core Algorithmic Approaches
- Dijkstra on stopping positions, with the path string as part of the state for tie-breaking.
- Pushing
(distance, path, r, c)into the heap makes equal distances break lexicographically on the path -- exactly the required rule. - The direction order must be
u, d, l, rso that the lexicographic comparison matches the problem's ordering. - The roll stops early if the ball passes over the hole, since it falls in.
💻 Benchmark Python3 Implementation
class Solution:
def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
import heapq
m, n = len(maze), len(maze[0])
# order matters: the heap compares (dist, path) so ties break lexicographically
dirs = [(-1, 0, "u"), (1, 0, "d"), (0, -1, "l"), (0, 1, "r")]
h = [(0, "", ball[0], ball[1])]
seen = set()
while h:
d, path, r, c = heapq.heappop(h)
if (r, c) in seen:
continue # settled with a shorter or better path
seen.add((r, c))
if [r, c] == hole:
return path
for dr, dc, ch in dirs:
nr, nc, steps = r, c, 0
while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
nr += dr
nc += dc
steps += 1
if [nr, nc] == hole: # falls in -> stop rolling
break
if (nr, nc) not in seen:
heapq.heappush(h, (d + steps, path + ch, nr, nc))
return "impossible"⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n * (m + n) log(m * n)): each stopping cell rolls four times.
💾 Space Complexity
O(m * n) for the visited set and the heap.
⚠️ Interview Pitfalls & Follow-ups
- Not stopping the roll at the hole: the ball would roll past it.
- Using a different direction order: the lexicographic tie-break would be wrong.
- Storing the path outside the heap: the tie-break requires it to be part of the comparison key.
- Marking visited when pushing: a shorter or lexicographically better path to the same cell could be missed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.