Skip to main content

1197 - Minimum Knight Moves

Difficulty: Medium | Pattern: BFS | Company tags: Amazon, Facebook, Uber

Problem Statement​

In an infinite chessboard with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves from its current position (x, y):

(x±1, y±2), (x±2, y±1)

Return the minimum number of steps needed to move the knight to [x, y].

Example 1:

Input: x = 2, y = 1
Output: 1

Example 2:

Input: x = 5, y = 5
Output: 4

Approach: BFS — O(|x|×|y|)​

Key insight: BFS from (0,0) finds the shortest path. Use symmetry: the knight moves symmetrically in all quadrants, so restrict search to the first quadrant by using abs(x), abs(y). Also, allow slightly negative coordinates (down to -2) to handle the case where approaching from below is needed.

from collections import deque

def minKnightMoves(x: int, y: int) -> int:
    x, y = abs(x), abs(y)  # symmetry: only first quadrant
    
    queue = deque([(0, 0, 0)])  # (r, c, steps)
    visited = {(0, 0)}
    
    moves = [(1,2),(2,1),(1,-2),(2,-1),(-1,2),(-2,1),(-1,-2),(-2,-1)]
    
    while queue:
        r, c, steps = queue.popleft()
        
        if r == x and c == y:
            return steps
        
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if (nr, nc) not in visited and nr >= -2 and nc >= -2:
                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))
    
    return -1

Why Allow -2?​

Due to symmetry we fold the target into the first quadrant using abs(x), abs(y). However, the optimal path to a near-origin target can briefly step to a negative coordinate — the shortest route to (1,1) passes through (2,-1). If we clamped the search to strictly non-negative coordinates, we would miss these routes and overcount. Allowing coordinates down to -2 gives the knight just enough room to make these maneuvers while keeping the search bounded.

Dry Run​

Target: (2,1)

  • Start: (0,0), steps=0
  • From (0,0): try all 8 moves. One of them: (1,2) → step 1; (2,1) → step 1 ✓

Target: (5,5)

BFS explores level by level. Path: 0→(2,1)→(4,2)→(3,4)→(5,5) = 4 moves ✓

Edge Cases​

  • (0,0) → return 0 (already at the target).
  • (1,1) → return 2. This is the classic tricky case. A knight cannot reach an adjacent-diagonal square in one move, but it can in two, for example (0,0) → (2,-1) → (1,1). Notice the intermediate square has a negative coordinate — this is exactly why the search must be allowed to dip slightly below zero rather than being strictly confined to the first quadrant.
  • (2,1) → return 1 (a single knight move).

Complexity​

  • Time: O(|x| × |y|) — number of cells in the bounded search area
  • Space: O(|x| × |y|) for visited set