Minimum Knight Moves

Ishaan S Published 24 Oct, 2026

A chess knight stands on square (0, 0) of a board that extends forever in every direction. In one move a knight travels two squares along one axis and one square along the other, so from (a, b) it can reach the eight squares (a ± 1, b ± 2) and (a ± 2, b ± 1).

Given a target square (x, y), return the minimum number of moves the knight needs to land on it. Every square can be reached.

Example 1

Input: x = 3, y = 3 Output: 2 Why: Two moves suffice: (0, 0) → (1, 2) → (3, 3).

Example 2

Input: x = -1, y = 0 Output: 3 Why: No single move reaches (-1, 0), and a knight changes square colour on every move, so the count must be odd. Three works: (0, 0) → (2, 1) → (1, -1) → (-1, 0).

Example 3

Input: x = 0, y = 0 Output: 0 Why: The knight is already on the target.

Constraints

-300 <= x, y <= 300
0 <= |x| + |y| <= 300

Pattern Path · Graphs: Traversal · problem 135 of 169

Every move costs the same, so "fewest moves" means shortest path in an unweighted graph whose nodes are squares.

Breadth-first search from (0, 0) explores squares in order of distance; the first time you reach the target, you have the answer.

The board is symmetric: (x, y), (-x, y) and (x, -y) need the same number of moves. Solve for (|x|, |y|).

With the target in the first quadrant, you never need to wander far into negative coordinates. Restricting the search to squares with both coordinates at least -2 keeps it small and still correct.

Target: O(max(|x|, |y|)2) time, O(max(|x|, |y|)2) extra space.

Start simple

Plain BFS over the whole plane around the origin, visiting every square within the answer's radius in all four quadrants: correct, but about four times the work, O(max(|x|, |y|)²).

The key idea

The squares form an unweighted graph in which each square connects to its eight knight moves, so breadth-first search finds the minimum: it visits all squares one move away, then all squares two moves away, and so on. The level on which the target first appears is the answer.

On an infinite board we must keep the search small. Reflections across either axis map knight moves to knight moves, so the distance to (x, y) equals the distance to (|x|, |y|). Now the target is in the first quadrant, and a shortest path never needs to go more than two squares below either axis: dips of one or two are needed near the origin (for example, reaching (1, 1) uses (2, -1)), but anything deeper could be reflected back for a path that is no longer. So we only enqueue squares whose coordinates are both at least -2, and a set of visited squares stops repeats.

BFS explores roughly a quarter disc whose radius is the target distance, which is O(|x| · |y|) squares in the worst case, comfortably fast for |x| + |y| <= 300.

Complexity

Time: O(max(|x|, |y|)2)
Space: O(max(|x|, |y|)2)

Python

class Solution:
    def minKnightMoves(self, x, y):
        MOVES = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
        target = (abs(x), abs(y))  # symmetry: solve in the first quadrant
        seen = {(0, 0)}
        frontier = [(0, 0)]
        moves = 0
        while target not in seen:
            moves += 1
            next_frontier = []
            for a, b in frontier:
                for da, db in MOVES:
                    square = (a + da, b + db)
                    # A shortest path never needs to go below -2 on either axis.
                    if square[0] >= -2 and square[1] >= -2 and square not in seen:
                        seen.add(square)
                        next_frontier.append(square)
            frontier = next_frontier
        return moves

JavaScript

var minKnightMoves = function(x, y) {
  const MOVES = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]];
  const tx = Math.abs(x), ty = Math.abs(y); // symmetry: solve in the first quadrant
  const key = (a, b) => a + "," + b;
  const seen = new Set([key(0, 0)]);
  let frontier = [[0, 0]];
  let moves = 0;
  while (!seen.has(key(tx, ty))) {
    moves++;
    const next = [];
    for (const [a, b] of frontier) {
      for (const [da, db] of MOVES) {
        const na = a + da, nb = b + db;
        // A shortest path never needs to go below -2 on either axis.
        if (na < -2 || nb < -2 || seen.has(key(na, nb))) continue;
        seen.add(key(na, nb));
        next.push([na, nb]);
      }
    }
    frontier = next;
  }
  return moves;
};

What the interviewer is checking

This tests whether you model a grid puzzle as shortest path in an unweighted graph and then use symmetry to prune an otherwise unbounded search.

Mistakes to avoid

Using DFS, which finds a path but not the shortest one.
Pruning to strictly non-negative coordinates: (1, 1) needs a step through (2, -1) and would come out wrong.
Marking squares visited when they are dequeued instead of enqueued, which floods the queue with duplicates.
Assuming a closed-form greedy formula without handling the special cases near the origin.

Follow-ups to expect

Make it faster for far targets. (Bidirectional BFS, or greedy then BFS.)
What if the board is finite, n × n? (BFS with bounds checks.)
Can you do it with memoised recursion? (dp(x, y) over |x-1|,|y-2| / |x-2|,|y-1|.)

In real software

Breadth-first search over a state space with uniform step cost is how puzzle solvers, grid pathfinding in games and robot motion planners find minimum-move solutions.

Practice next

Topics #135 #t-graph-traversal BFS Math Matrix Medium Practice