1197. Minimum Knight Moves
Asked at Databricks, Uber
Difficulty
Medium
Time
O(max^2)
Space
O(max^2)
Pattern
Breadth-First Search
Companies
2
Problem
A knight starts on square [0, 0] of an infinite chess board. Coordinates can be any integers, positive or negative. A knight move goes two squares in one direction, then one square at a right angle — for example (+2, +1) or (-1, +2). There are 8 such moves in total.
Given a target square [x, y], return the smallest number of knight moves needed to go from [0, 0] to [x, y]. The answer always exists, so you never need to report failure.
Every move costs the same, so a breadth-first search (BFS) from the start gives the shortest path. The board is infinite, so you cannot build a full grid. Instead keep a hash set of visited squares, and only store squares you actually reach.
One knight move from the start
Constraints
- ●
-300 <= x, y <= 300 - ●
0 <= |x| + |y| <= 300
Examples
x = 2, y = 11x = 5, y = 54Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
Key insight: BFS on the infinite board. A knight has 8 possible moves: (+2,+1), (+2,-1), (-2,+1), (-2,-1), (+1,+2), (+1,-2), (-1,+2), (-1,-2). BFS guarantees the shortest path.
You cannot create an infinite grid. Use a hash set to store visited positions as tuples (x, y). This way, the space is proportional to the number of visited cells, not the board size.
Optimization: the target is at most 300 away (per constraints). You only need to explore positions within a bounded region. Since a knight moves at most 2 squares per move, the BFS frontier grows roughly as a diamond shape. Prune positions that are too far from the target.
Symmetry optimization: the board is symmetric. The minimum moves to (x, y) is the same as to (|x|, |y|), (y, x), (-x, y), etc. You can always work in the first quadrant. Map the target to (|x|, |y|) first.
Edge cases: target (0, 0) requires 0 moves. Target (1, 0) or (0, 1) requires 3 moves (a knight cannot reach an adjacent square in fewer). Target (1, 1) also requires 2 moves.
Optimal Approach
BFS from (0, 0) toward (targetX, targetY). Use a hash set for visited positions.
- Start with queue = [(0, 0, 0)] (x, y, steps). Mark (0, 0) as visited.
- While queue is not empty:
- Dequeue (x, y, steps).
- If (x, y) == (targetX, targetY), return steps.
- For each of the 8 knight moves, compute new position (nx, ny).
- If (nx, ny) not visited, add to queue and mark visited.
- Return -1 (should never reach here for valid targets).
Optimization: use symmetry to map target to first quadrant. Only explore positions where |x| <= max+2 and |y| <= max+2.
Time: O(max^2) where max = max(|targetX|, |targetY|). Each cell is visited once. Space: O(max^2) for the visited set.
BFS layer by layer
What Trips People Up in Real Interviews
Trying to use a fixed-size grid instead of a hash set. The board is infinite, so you cannot allocate a 2D array. Use a HashSet or Set with coordinate tuples as keys.
Forgetting that the board is infinite. You cannot precompute all distances. BFS explores outward from (0,0) until it reaches the target, expanding only the cells it visits.
Not pruning unreachable cells. The BFS will explore far beyond the target if you don't bound the search. Use symmetry (work in first quadrant) and limit exploration to a reasonable range.
Using A* or heuristic search when BFS is simpler. The knight has uniform move cost (each move costs 1), so BFS guarantees the shortest path. A* is overkill unless the board is extremely large.
Handling negative coordinates incorrectly. The board extends to negative coordinates. A knight at (0,0) can move to (-1,-2). Your hash set must support negative keys — tuples work naturally.
Solution Code
O(max^2) timefrom collections import deque
def minKnightMoves(x, y):
if x == 0 and y == 0:
return 0
moves = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
queue = deque([(0, 0, 0)])
visited = {(0, 0)}
while queue:
cx, cy, dist = queue.popleft()
for dx, dy in moves:
nx, ny = cx + dx, cy + dy
if (nx, ny) == (x, y):
return dist + 1
if (nx, ny) not in visited:
visited.add((nx, ny))
queue.append((nx, ny, dist + 1))Frequently Asked Questions
What is the Minimum Knight Moves problem?
Find the minimum number of moves for a chess knight to reach a target square on an infinite 2D board from (0, 0). Use BFS since all moves have equal cost. The infinite board means you cannot precompute a fixed grid.
How do you solve Minimum Knight Moves?
The optimal approach runs in O(max^2) time and O(max^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Knight Moves?
Minimum Knight Moves is asked at Databricks, Uber. It is a medium difficulty problem.
What are common mistakes on Minimum Knight Moves?
- Trying to use a fixed-size grid instead of a `hash set`. The board is infinite, so you cannot allocate a 2D array. Use a `HashSet` or `Set` with coordinate tuples as keys.
- Forgetting that the board is infinite. You cannot precompute all distances. BFS explores outward from (0,0) until it reaches the target, expanding only the cells it visits.
- Not pruning unreachable cells. The BFS will explore far beyond the target if you don't bound the search. Use symmetry (work in first quadrant) and limit exploration to a reasonable range.
- Using A* or heuristic search when BFS is simpler. The knight has uniform move cost (each move costs 1), so BFS guarantees the shortest path. A* is overkill unless the board is extremely large.
- Handling negative coordinates incorrectly. The board extends to negative coordinates. A knight at (0,0) can move to (-1,-2). Your `hash set` must support negative keys — tuples work naturally.