In an infinite chess board with coordinates from -infinity to +infinity, a knight starts at (0, 0). Return the minimum number of moves to reach (x, y).

A knight moves in an “L” shape: 2 squares in one direction and 1 square perpendicular (8 possible moves).

Examples

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: (0,0) → (2,1)

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: (0,0) → (2,1) → (4,2) → (3,4) → (5,5)

Constraints

  • -300 <= x, y <= 300

Thinking Process

Why BFS?

We need the minimum number of moves from (0,0) to (x,y) on an unweighted graph where each cell connects to 8 neighbors via knight moves. This is classic BFS shortest path.

Symmetry Optimization

Knight moves are symmetric across both axes. If (x, y) is reachable in k moves, so is (-x, y), (x, -y), and (-x, -y). So we can fold the target into the first quadrant with x = abs(x), y = abs(y) and only explore that region.

Why Allow nx >= -1 and ny >= -1?

For small targets like (1,0), the knight must briefly step into negative coordinates to reach them:

(0,0) → (1,-2) → (-1,-1) → ... or more typically:
(0,0) → (-1,2) → (1,1) → ... → (1,0)

Allowing coordinates down to -1 (not -2 or beyond) is sufficient because after folding to the first quadrant, we never need to go further than one step past the origin.

Algorithm

  1. Fold target to first quadrant: x = abs(x), y = abs(y)
  2. BFS from (0,0) with all 8 knight moves
  3. Prune: only enqueue positions with nx >= -1 and ny >= -1
  4. Track visited states to avoid revisits
  5. Return steps when we reach (x, y)
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Queue BFS (this problem) O(n) O(n) Shortest path in unweighted graphs
Multi-source BFS O(n) O(n) Start from all sources simultaneously
0-1 BFS / deque O(n) O(n) Weights 0 or 1
Level-order BFS O(n) O(w) Process by depth/layer

Solution

from collections import deque


class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x, y = abs(x), abs(y)
        dirs = (
            (2, 1), (1, 2), (-1, 2), (-2, 1),
            (-2, -1), (-1, -2), (1, -2), (2, -1),
        )
        q = deque([(0, 0)])
        vis = {(0, 0): 0}

        while q:
            cx, cy = q.popleft()
            steps = vis[(cx, cy)]
            if cx == x and cy == y:
                return steps
            for dx, dy in dirs:
                nx, ny = cx + dx, cy + dy
                if nx >= -1 and ny >= -1 and (nx, ny) not in vis:
                    vis[(nx, ny)] = steps + 1
                    q.append((nx, ny))
        return -1

Solution Explanation

Approach: Queue BFS (this problem)

Key idea: ### Why BFS?

How the code works:

  1. Fold target to first quadrant: x = abs(x), y = abs(y)
  2. BFS from (0,0) with all 8 knight moves
  3. Prune: only enqueue positions with nx >= -1 and ny >= -1
  4. Track visited states to avoid revisits
  5. Return steps when we reach (x, y)

Walkthrough — input x = 2, y = 1, expected output 1:

(0,0) → (2,1)

Common Mistakes

  • Not using abs(x), abs(y) to exploit symmetry – BFS explores 4x the area unnecessarily
  • Restricting to nx >= 0, ny >= 0 – misses paths that need to briefly dip into negative coordinates
  • Using an unordered_set on pair directly (C++ doesn’t provide a default hash for pair)

Key Takeaways

  • “Minimum moves on a grid with special movement rules” = BFS
  • Symmetry pruning (fold to first quadrant) dramatically reduces the search space
  • Allowing -1 boundary is a subtle but critical detail for correctness near the origin

References

Template Reference