NeetCode #612LC-1197MediumGraphsNC Algo100
← Back to All Problems#612 · #1197 · Minimum Knight Moves(进击的骑士)
📌 Problem Statement & Constraints
A knight moves on an infinite chessboard. Given
x and y, return the minimum number of moves to reach (x, y) from (0, 0). Constraints: -300 <= x, y <= 300.💡 Core Algorithmic Approaches
- BFS over the board, but the board is infinite -- so bound the search using symmetry and a margin.
- Symmetry: take
x = abs(x)andy = abs(y), so the target is in the first quadrant. - Bound the search to
[-2, x+2] x [-2, y+2]: a shortest path never needs to go far outside. - The margin of 2 is what allows the knight to go around when needed.
💻 Benchmark Python3 Implementation
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
from collections import deque
x, y = abs(x), abs(y) # symmetry -> first quadrant
moves = ((1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2))
q = deque([(0, 0, 0)])
seen = {(0, 0)}
while q:
r, c, d = q.popleft()
if (r, c) == (x, y):
return d
for dr, dc in moves:
nr, nc = r + dr, c + dc
# a shortest path never needs to go more than 2 outside the box
if -2 <= nr <= x + 2 and -2 <= nc <= y + 2 and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(x * y): the bounded box has at most (x+5) * (y+5) cells.
💾 Space Complexity
O(x * y) for the visited set.
⚠️ Interview Pitfalls & Follow-ups
- BFS on an unbounded board: it would never terminate.
- Using
0 <= nr <= xas the bound: the knight sometimes must overshoot and come back, hence the margin of 2. - Forgetting the symmetry reduction: the box would be four times larger.
- Assuming the knight can reach any cell in O(1): the BFS is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.