Minimum Knight Moves

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

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

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]

Let's solve the Knight Minimum Moves on an Infinite Chessboard problem using your signature format:

---

✅ 1. Problem Explanation (In Simple Terms)

You have a knight at position [0, 0] on an infinite chessboard.

You're given a target coordinate [x, y].

Your task: return the minimum number of moves the knight needs to reach [x, y].

---

💡 2. Key Insights

1. Knight Moves:

   • A knight moves in 8 possible ways:

       (+1,+2), (+1,-2), (-1,+2), (-1,-2),
       (+2,+1), (+2,-1), (-2,+1), (-2,-1)
     

2. Symmetry:

   • The board is symmetric across both x and y axes.

   • So instead of solving for (x, y), we can solve for (abs(x), abs(y)) to simplify the problem.

   • This drastically reduces the search space.

3. Use BFS:

   • Since we're finding the shortest path in an unweighted grid, BFS is optimal.

   • We'll use a queue to simulate the knight's movement level by level.

4. Early Pruning:

   • The knight's pattern allows us to bound the search (e.g., you never need to explore beyond (x + 2, y + 2)).

---

🧠 3. Steps to Solve

1. Take the absolute value of x and y (due to symmetry).

2. Initialize a queue for BFS: starting from [0, 0] with 0 moves.

3. Use a Set to track visited positions to avoid cycles.

4. For each position:

   • Try all 8 knight moves.

   • If a move lands on (x, y), return the number of steps.

   • Otherwise, enqueue the position if it hasn’t been visited.

5. BFS ensures we find the shortest path.

---

✅ 4. JavaScript Code (Clean & Optimized)

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
function minKnightMoves(x, y) {
  x = Math.abs(x);
  y = Math.abs(y);

  const directions = [
    [1, 2], [2, 1], [-1, 2], [-2, 1],
    [-1, -2], [-2, -1], [1, -2], [2, -1]
  ];

  const visited = new Set();
  const queue = [[0, 0, 0]]; // [x, y, moves]

  while (queue.length > 0) {
    const [curX, curY, steps] = queue.shift();

    if (curX === x && curY === y) return steps;

    for (const [dx, dy] of directions) {
      const nx = curX + dx;
      const ny = curY + dy;
      const key = `${nx},${ny}`;

      // limit the search space for optimization
      if (!visited.has(key) && nx >= -2 && ny >= -2 && nx <= x + 2 && ny <= y + 2) {
        visited.add(key);
        queue.push([nx, ny, steps + 1]);
      }
    }
  }

  return -1; // unreachable, theoretically never happens on an infinite board
}

---

🔍 5. Dry Run Example

Input: x = 2, y = 1

→ Symmetry: (2,1)
→ Start at (0,0)

→ One of knight's valid moves is (2,1) in one step.

✅ Output: 1

---

⏱️ 6. Time & Space Complexity

Let d = distance from origin to (x, y)

• Time Complexity: O(d^2) in worst case due to BFS exploring a 2D area

• Space Complexity: O(d^2) for queue and visited set

But in practice, pruning + symmetry makes it extremely fast even for large targets.

---

✅ Final Verdict

• Fast, elegant BFS with symmetry optimization

• Solves the infinite grid knight move problem efficiently

• Can be extended to output the actual path if needed

---