Leetcode 1197. Minimum Knight Moves
Asked at:
Uber
Meta
DESCRIPTION
Given target coordinates (x, y), find the minimum number of knight moves required to reach that square from (0, 0) on an infinite chessboard. A knight moves in an L-shape: two squares in one direction and one square perpendicular (8 possible moves). For example, reaching (2, 1) requires exactly 1 move, while (5, 5) requires 4 moves.
Input:
x = 2, y = 1
Output:
1
Explanation: One knight move from (0,0) directly reaches (2,1)
Constraints:
- |x|, |y| ≤ 300 (coordinates can be negative)
- Chessboard is infinite in all directions
- Knight moves follow standard chess rules (L-shaped: ±2 in one axis, ±1 in perpendicular axis)
Understanding the Problem
This is a shortest-path problem on an implicit unweighted graph where each square is a node and knight moves are edges. The challenge is that the graph is infinite, so naive BFS could explore indefinitely. The key insight is exploiting symmetry: all four quadrants are equivalent due to absolute value symmetry, and within the first quadrant, we can use BFS with pruning or mathematical patterns to find the minimum distance efficiently.
Building Intuition
A naive BFS from (0,0) works but may explore many unnecessary squares, especially for large coordinates. The optimized approach exploits symmetry by converting (x, y) to (|x|, |y|) (first quadrant), then using BFS with bounds or bidirectional search to limit exploration. For example, reaching (-5, -5) is identical to reaching (5, 5) due to symmetry, reducing the search space by 4×.
Knight move problems appear in game AI (chess engines), robotics path planning (discrete movement constraints), and graph theory (understanding shortest paths on regular grids). The symmetry optimization technique generalizes to other grid-based pathfinding problems with symmetric movement patterns.
Common Pitfalls
Implementation
BFS Core Implementation
Implement breadth-first search starting from (0, 0) to find the shortest path to (x, y). Use a queue to explore positions level-by-level, tracking visited squares to avoid cycles. Exploit symmetry by converting target to (|x|, |y|) so we only search the first quadrant. For example, BFS for (5, 5) explores (0,0) → (2,1), (1,2) → (4,2), (3,3), (3,1), (0,4) → ... until reaching (5,5) at depth 4.
from collections import dequedef knight_moves(x, y):x, y = abs(x), abs(y)if (x, y) == (0, 0):return 0queue = deque([(0, 0, 0)])visited = {(0, 0)}moves = [(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)]while queue:cx, cy, dist = queue.popleft()for dx, dy in moves:nx, ny = cx + dx, cy + dyif (nx, ny) == (x, y):return dist + 1if (nx, ny) not in visited and -2 <= nx <= x+2 and -2 <= ny <= y+2:visited.add((nx, ny))queue.append((nx, ny, dist + 1))
Knight Move Generator
Create a helper function that generates all 8 valid knight moves from a given position (cx, cy). The moves are (cx±2, cy±1) and (cx±1, cy±2), yielding 8 neighbors. This function is called by the BFS in Section 1 to explore next positions. For example, from (2, 1), it generates [(4,2), (4,0), (0,2), (0,0), (3,3), (3,-1), (1,3), (1,-1)].
def get_knight_moves(cx, cy):"""Generate all 8 valid knight moves from position (cx, cy)."""moves = [(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)]return [(cx + dx, cy + dy) for dx, dy in moves]
Optimization with Bounds
Enhance the BFS from Section 1 by adding search bounds to prevent infinite exploration. Limit the search space to coordinates within max(|x|, |y|) + 4 in each direction, as the optimal path rarely exceeds this bound. This prunes unnecessary branches early, improving performance for large targets. For example, when targeting (5, 5), only explore positions where cx, cy ≤ 9, reducing the visited set significantly.
def knight_moves_bounded(x, y):x, y = abs(x), abs(y)if (x, y) == (0, 0):return 0bound = max(x, y) + 4queue = deque([(0, 0, 0)])visited = {(0, 0)}moves = [(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)]while queue:cx, cy, dist = queue.popleft()for dx, dy in moves:nx, ny = cx + dx, cy + dyif (nx, ny) == (x, y):return dist + 1if (nx, ny) not in visited and abs(nx) <= bound and abs(ny) <= bound:visited.add((nx, ny))queue.append((nx, ny, dist + 1))
What We've Learned
- Pattern: BFS on implicit graphs with symmetry exploitation reduces search space by 4× (use absolute values)
- Use Case: Grid pathfinding with constrained movement (chess, robotics, game AI)
- Optimization: Bounding the search space prevents infinite exploration on unbounded grids
- Technique: Bidirectional BFS or A* with Manhattan distance heuristic can further optimize for very large coordinates
Problems to Practice
medium
This is the exact same problem as the one being analyzed. It involves finding the minimum number of knight moves on a chessboard using BFS, exploiting symmetry to optimize the solution.
medium
Similar shortest-path problem on a grid using BFS with multi-source traversal. Both problems involve finding minimum steps/time to reach target states on a matrix, teaching the same BFS pattern for grid-based shortest path problems.
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid May, 2026
Uber
Mid-level
Mid April, 2026
Meta
Senior
Early April, 2026
Mid-level
Hello Interview Premium
Your account is free and you can post anonymously if you choose.