Minimum Knight Moves (LeetCode 1197)
Picture a chessboard that stretches infinitely in every direction, coordinates running from -infinity to +infinity, with a single knight sitting at square [0, 0].
The knight only ever makes the usual 8 knight jumps: two squares along one axis, then one square along the other. Find the fewest such jumps needed to land the knight exactly on square [x, y]; you can assume a path always exists.
Worked Examples
x = 2, y = 11x = 5, y = 54⚖️Formal Constraints & Bounds
-300 <= x, y <= 3000 <= |x| + |y| <= 300
Core Insight
An unbounded board forces visited into a hash set instead of an array, and quadrant-fold symmetry plus a small negative margin keep the search both correct and bounded.
Real-World Scenario & Production Applications
Chess engines computing 'mate in N' knight-only reachability puzzles, and game AI evaluating minimum-move reachability across unbounded virtual maps.
Step-by-Step Execution Trace Table
Ring 0: (0,0) [steps=0]Ring 1: (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2) [steps=1]Ring 2: ... includes (3,3), (4,2), (2,4) among others [steps=2]Ring 3: ... includes (4,4), (3,5), (5,3) among others [steps=3]Ring 4: ... includes (5,5) — TARGET FOUND [steps=4] Step-by-Step Wavefront Progression (target = (5, 5))
- Step 1 (Fold & Seed, Ring 0, d=0): Target
(5, 5)is already in the first quadrant, sox, y = 5, 5unchanged.queue = [(0, 0, 0)],visited = {(0, 0)}. - Step 2 (Dequeue (0,0), Expand 8 Knight Jumps, d=0): Pop
(0, 0, steps=0). Not the target. Enqueue all 8 reachable cells:(1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2), each withsteps=1. Mark each on enqueue. - Step 3 (Dequeue Ring 1 cells, Expand Ring 2, d=1): Pop each ring-1 cell in turn. From
(2,1), the jump(1,2)reaches(3,3); from(1,2), the jump(2,1)also reaches(3,3)but it is already marked visited from the first discovery — the mark-on-enqueue guard prevents a duplicate insertion. Ring 2 accumulates cells including(3,3),(4,2),(2,4), each withsteps=2. - Step 4 (Dequeue Ring 2 cells, Expand Ring 3, d=2): Pop each ring-2 cell. From
(3,3), the jump(2,1)reaches(5,4); the jump(1,2)reaches(4,5). Ring 3 accumulates cells including(4,4),(5,3),(3,5),(5,4),(4,5), each withsteps=3. None equal(5, 5)yet. - Step 5 (Dequeue Ring 3 cells, Discover Target, d=3): Pop each ring-3 cell. From
(3,4)(in ring 3 via a different path) the jump(2,1)reaches(5,5). Enqueue(5, 5, steps=4). - Step 6 (Dequeue (5,5), Target Reached, d=4): Pop
(5, 5, steps=4).(r, c) == (x, y)— goal check succeeds. Search Complete: return4✅.
x = 2, y = 1Expected:1| 1 | x, y = abs(x), abs(y) |
| 2 | queue = deque([(0, 0, 0)]) |
| 3 | visited = {(0, 0)} |
| 4 | while queue: |
| 5 | r, c, steps = queue.popleft() |
| 6 | if (r, c) == (x, y): |
| 7 | return steps |
| 8 | for dr, dc in moves: |
| 9 | nr, nc = r + dr, c + dc |
| 10 | if nr >= -2 and nc >= -2 and (nr, nc) not in visited: |
| 11 | visited.add((nr, nc)) |
| 12 | queue.append((nr, nc, steps + 1)) |
| 13 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A chess knight on an infinite chessboard moves in an "L-shape": 2 squares along one axis and 1 square along the perpendicular axis (8 possible moves). Finding the minimum jumps to reach from on an infinite board presents a major challenge: unlike bounded grids, an infinite plane has no walls, making brute-force BFS prone to Memory Limit Exceeded (MLE). The key observation is quadrant symmetry: because a knight's moves are completely symmetrical across the -axis, -axis, and diagonal, the shortest path to , , , and are mathematically identical. We can fold the entire infinite plane into the positive quadrant by taking .
🏟️ The Analogy: Folding an Origami Map into Quadrants
Imagine holding an infinite square map of a city with at the intersection of two endless perpendicular avenues. If someone asks for the shortest driving distance to , you don't drive south-west into the dark; you fold the map along the vertical and horizontal avenues until all four quadrants overlap perfectly on top of Quadrant 1. The distance to is identical, reducing the area you need to search to one-quarter of the plane.
🔑 Why It Works
Notice the boundary guard nr >= -2 and nc >= -2. A knight starting at heading to must jump out to or before landing on in 2 steps. Allowing a small buffer of guarantees optimal routing while preventing negative infinity wander.
Exploring all 4 quadrants symmetrically: Knight movements are symmetric across all 4 quadrants. Failing to work with
abs(x), abs(y)expands the search space 4x unnecessarily.Pruning coordinates into negative space: The knight sometimes needs to hop into negative coordinates (e.g. requires stepping through ). Pruning strictly at prunes valid paths.
Unbounded coordinate explosion: Without pruning
x + y > 300or bidirectional BFS, search frontier grows exponentially.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Unbounded / infinite coordinate space + minimum moves of a fixed move-set (knight jumps).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: quadrant symmetry means distance(x, y) == distance(|x|, |y|); visited must be a hash set, not an array.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Clamping to r >= 0, c >= 0 instead of a small negative margin, which prunes valid detours near the axes.
Allocating a fixed-size visited array as if this were a bounded grid problem.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I fold the target into the first quadrant by symmetry, then run standard BFS from (0,0) over the 8 knight jumps, using a hash set for visited since the board is unbounded, with a small negative-coordinate margin to keep near-axis detours reachable. Runs in O(k^2) time where k is the max target coordinate."
Complexity & Mathematical Proof
O(X · Y)
Look at the execution steps: BFS from (0, 0) using 8 knight moves. Symmetry reduces search to first quadrant (abs(x), abs(y)), exploring bounded quadrant cells until (x, y) reached.
O(X · Y) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Visited set storing coordinate pairs in bounded radius.
T(X, Y) = O(|X| · |Y|)
Derivation Progression
(x, y) → (|x|, |y|)
Folds 4 quadrants into first quadrant, reducing state space by 4x.
(± 1, ± 2), (± 2, ± 1)
Generates 8 knight move candidates in O(1).
O(|X| · |Y|) visited states
Explores bounded box surrounding origin and target.
Variable Definitions
Absolute horizontal distance to target coordinate
Absolute vertical distance to target coordinate
Memory Architecture & Bounds
O(1) Iterative
O(|X| · |Y|) Visited coordinate set and BFS queue
O(1) Step count integer
Boundary Best / Worst Cases
for small coordinates.
.
for larger coordinates.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "knight moves on infinite chessboard", "minimum moves". 8 L-shaped moves: and . An experienced SWE exploits geometric symmetry: fold target coordinates into the first quadrant (abs(x), abs(y)) and bound the search space to to prevent unbounded exploration.
Coordinates up to . Bounded quadrant BFS runs in time.
Double-back moves near the origin: reaching requires stepping to then back to (2 moves). Allowing a small negative coordinate buffer (e.g. ) is essential.
Minimum Knight Moves (LeetCode 1197)
Picture a chessboard that stretches infinitely in every direction, coordinates running from -infinity to +infinity, with a single knight sitting at square [0, 0].
The knight only ever makes the usual 8 knight jumps: two squares along one axis, then one square along the other. Find the fewest such jumps needed to land the knight exactly on square [x, y]; you can assume a path always exists.
Worked Examples
x = 2, y = 11x = 5, y = 54⚖️Formal Constraints & Bounds
-300 <= x, y <= 3000 <= |x| + |y| <= 300
Core Insight
An unbounded board forces visited into a hash set instead of an array, and quadrant-fold symmetry plus a small negative margin keep the search both correct and bounded.
Real-World Scenario & Production Applications
Chess engines computing 'mate in N' knight-only reachability puzzles, and game AI evaluating minimum-move reachability across unbounded virtual maps.
Step-by-Step Execution Trace Table
Ring 0: (0,0) [steps=0]Ring 1: (1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2) [steps=1]Ring 2: ... includes (3,3), (4,2), (2,4) among others [steps=2]Ring 3: ... includes (4,4), (3,5), (5,3) among others [steps=3]Ring 4: ... includes (5,5) — TARGET FOUND [steps=4] Step-by-Step Wavefront Progression (target = (5, 5))
- Step 1 (Fold & Seed, Ring 0, d=0): Target
(5, 5)is already in the first quadrant, sox, y = 5, 5unchanged.queue = [(0, 0, 0)],visited = {(0, 0)}. - Step 2 (Dequeue (0,0), Expand 8 Knight Jumps, d=0): Pop
(0, 0, steps=0). Not the target. Enqueue all 8 reachable cells:(1,2), (2,1), (2,-1), (1,-2), (-1,-2), (-2,-1), (-2,1), (-1,2), each withsteps=1. Mark each on enqueue. - Step 3 (Dequeue Ring 1 cells, Expand Ring 2, d=1): Pop each ring-1 cell in turn. From
(2,1), the jump(1,2)reaches(3,3); from(1,2), the jump(2,1)also reaches(3,3)but it is already marked visited from the first discovery — the mark-on-enqueue guard prevents a duplicate insertion. Ring 2 accumulates cells including(3,3),(4,2),(2,4), each withsteps=2. - Step 4 (Dequeue Ring 2 cells, Expand Ring 3, d=2): Pop each ring-2 cell. From
(3,3), the jump(2,1)reaches(5,4); the jump(1,2)reaches(4,5). Ring 3 accumulates cells including(4,4),(5,3),(3,5),(5,4),(4,5), each withsteps=3. None equal(5, 5)yet. - Step 5 (Dequeue Ring 3 cells, Discover Target, d=3): Pop each ring-3 cell. From
(3,4)(in ring 3 via a different path) the jump(2,1)reaches(5,5). Enqueue(5, 5, steps=4). - Step 6 (Dequeue (5,5), Target Reached, d=4): Pop
(5, 5, steps=4).(r, c) == (x, y)— goal check succeeds. Search Complete: return4✅.
x = 2, y = 1Expected:1| 1 | x, y = abs(x), abs(y) |
| 2 | queue = deque([(0, 0, 0)]) |
| 3 | visited = {(0, 0)} |
| 4 | while queue: |
| 5 | r, c, steps = queue.popleft() |
| 6 | if (r, c) == (x, y): |
| 7 | return steps |
| 8 | for dr, dc in moves: |
| 9 | nr, nc = r + dr, c + dc |
| 10 | if nr >= -2 and nc >= -2 and (nr, nc) not in visited: |
| 11 | visited.add((nr, nc)) |
| 12 | queue.append((nr, nc, steps + 1)) |
| 13 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A chess knight on an infinite chessboard moves in an "L-shape": 2 squares along one axis and 1 square along the perpendicular axis (8 possible moves). Finding the minimum jumps to reach from on an infinite board presents a major challenge: unlike bounded grids, an infinite plane has no walls, making brute-force BFS prone to Memory Limit Exceeded (MLE). The key observation is quadrant symmetry: because a knight's moves are completely symmetrical across the -axis, -axis, and diagonal, the shortest path to , , , and are mathematically identical. We can fold the entire infinite plane into the positive quadrant by taking .
🏟️ The Analogy: Folding an Origami Map into Quadrants
Imagine holding an infinite square map of a city with at the intersection of two endless perpendicular avenues. If someone asks for the shortest driving distance to , you don't drive south-west into the dark; you fold the map along the vertical and horizontal avenues until all four quadrants overlap perfectly on top of Quadrant 1. The distance to is identical, reducing the area you need to search to one-quarter of the plane.
🔑 Why It Works
Notice the boundary guard nr >= -2 and nc >= -2. A knight starting at heading to must jump out to or before landing on in 2 steps. Allowing a small buffer of guarantees optimal routing while preventing negative infinity wander.
Exploring all 4 quadrants symmetrically: Knight movements are symmetric across all 4 quadrants. Failing to work with
abs(x), abs(y)expands the search space 4x unnecessarily.Pruning coordinates into negative space: The knight sometimes needs to hop into negative coordinates (e.g. requires stepping through ). Pruning strictly at prunes valid paths.
Unbounded coordinate explosion: Without pruning
x + y > 300or bidirectional BFS, search frontier grows exponentially.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Unbounded / infinite coordinate space + minimum moves of a fixed move-set (knight jumps).
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: quadrant symmetry means distance(x, y) == distance(|x|, |y|); visited must be a hash set, not an array.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Clamping to r >= 0, c >= 0 instead of a small negative margin, which prunes valid detours near the axes.
Allocating a fixed-size visited array as if this were a bounded grid problem.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I fold the target into the first quadrant by symmetry, then run standard BFS from (0,0) over the 8 knight jumps, using a hash set for visited since the board is unbounded, with a small negative-coordinate margin to keep near-axis detours reachable. Runs in O(k^2) time where k is the max target coordinate."
Complexity & Mathematical Proof
O(X · Y)
Look at the execution steps: BFS from (0, 0) using 8 knight moves. Symmetry reduces search to first quadrant (abs(x), abs(y)), exploring bounded quadrant cells until (x, y) reached.
O(X · Y) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Visited set storing coordinate pairs in bounded radius.
T(X, Y) = O(|X| · |Y|)
Derivation Progression
(x, y) → (|x|, |y|)
Folds 4 quadrants into first quadrant, reducing state space by 4x.
(± 1, ± 2), (± 2, ± 1)
Generates 8 knight move candidates in O(1).
O(|X| · |Y|) visited states
Explores bounded box surrounding origin and target.
Variable Definitions
Absolute horizontal distance to target coordinate
Absolute vertical distance to target coordinate
Memory Architecture & Bounds
O(1) Iterative
O(|X| · |Y|) Visited coordinate set and BFS queue
O(1) Step count integer
Boundary Best / Worst Cases
for small coordinates.
.
for larger coordinates.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "knight moves on infinite chessboard", "minimum moves". 8 L-shaped moves: and . An experienced SWE exploits geometric symmetry: fold target coordinates into the first quadrant (abs(x), abs(y)) and bound the search space to to prevent unbounded exploration.
Coordinates up to . Bounded quadrant BFS runs in time.
Double-back moves near the origin: reaching requires stepping to then back to (2 moves). Allowing a small negative coordinate buffer (e.g. ) is essential.