Minimum Knight Moves

35 min · minKnightMoves()

A knight ignores the streets between squares. It jumps in an L, lands, and asks the same question again: what's the fewest number of jumps from home to here?

A knight starts at (0, 0) on an infinite chessboard. Given integer coordinates (x, y), return the minimum number of knight moves needed to land there.

Each move changes position by one of these eight offsets:

(±2, ±1), or
(±1, ±2).

The signs are independent, so all four direction combinations count. The board has no edges or blocked squares, and reaching (0, 0) takes 0 moves.

Constraints

-300 <= x <= 300
-300 <= y <= 300
x and y are integers.

Hints

Search by move count

From the origin, generate every square reachable in one move, then two moves, then three. The first time you see the target gives the minimum.

The board repeats itself

Reflecting a route across either axis, or swapping its coordinates, doesn't change its length. You only need to solve for x >= y >= 0.

Keep a small safety margin

A shortest route may briefly step past an axis, especially near the origin. Allow coordinates down to -2, and stop exploring more than two squares past the folded target.

Follow-up

Could a search starting from both the origin and the target reduce the number of board states you visit for faraway coordinates?

Visible cases

Examples

Example 1

ready

Input: x = 2 y = 1
Expected: 1
Why: (2, 1) is one legal knight jump

Example 2

ready

Input: x = 5 y = 5
Expected: 4
Why: no route uses fewer than four jumps

Example 3

ready

Input: x = 0 y = 0
Expected: 0
Why: the knight already occupies the target

Interview signal

Asked at

AmazonGoogle

Unbounded BFS

Treat every coordinate as a node with eight outgoing edges. State-space BFS is breadth-first search where a complete situation — here, a board coordinate — is one search state. Since every knight jump costs one move, the first visit to the target is optimal.

from collections import deque
 
 
def min_knight_moves(x: int, y: int) -> int:
    moves = (
        (2, 1), (2, -1), (-2, 1), (-2, -1),
        (1, 2), (1, -2), (-1, 2), (-1, -2),
    )
    queue = deque([(0, 0, 0)])
    seen = {(0, 0)}
 
    while queue:
        col, row, distance = queue.popleft()
        if (col, row) == (x, y):
            return distance
        for dc, dr in moves:
            next_position = (col + dc, row + dr)
            if next_position not in seen:
                seen.add(next_position)
                queue.append((*next_position, distance + 1))
 
    return -1

This eventually reaches every target, but it explores the expanding circle in all four quadrants even when one folded quadrant contains all the information.

Time O(d²), where d is the answer — the reachable region's area grows with the square of its radius. Space O(d²) for the queue and visited coordinates.

Symmetry-bounded state-space BFS

A knight's moves are unchanged by horizontal reflection, vertical reflection, or swapping the axes. Fold the target with absolute values, then swap its coordinates so target_x >= target_y >= 0.

We still need a small negative margin. Near the origin, a shortest route to (1, 0) or (1, 1) temporarily crosses an axis. Keeping coordinates from -2 through two squares past the target preserves those turns without opening the infinite board.

from collections import deque
 
 
def min_knight_moves(x: int, y: int) -> int:
    target_x, target_y = sorted((abs(x), abs(y)), reverse=True)
    moves = (
        (2, 1), (2, -1), (-2, 1), (-2, -1),
        (1, 2), (1, -2), (-1, 2), (-1, -2),
    )
    queue = deque([(0, 0, 0)])
    seen = {(0, 0)}
 
    while queue:
        col, row, distance = queue.popleft()
        if (col, row) == (target_x, target_y):
            return distance
        for dc, dr in moves:
            next_col, next_row = col + dc, row + dr
            if not (-2 <= next_col <= target_x + 2):
                continue
            if not (-2 <= next_row <= target_y + 2):
                continue
            if (next_col, next_row) in seen:
                continue
            seen.add((next_col, next_row))
            queue.append((next_col, next_row, distance + 1))
 
    return -1

Time O((|x|+1)(|y|+1)) for the bounded rectangle, after folding and swapping the coordinates. Space O((|x|+1)(|y|+1)) for its queue and visited set. The +1 terms absorb the fixed two-cell margins and the near-axis cases.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayx: int · y: int

Expected

Run: visible + custom · Submit: full suite