Log inSign up
mediumLeetCodeNot Started

Minimum Knight Moves

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

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

A knight has 8 possible moves: (r ± 1, c ± 2) and (r ± 2, c ± 1).

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

---

### Examples

Example 1: ``text Input: x = 2, y = 1 Output: 1 Explanation: [0, 0] -> [2, 1] in 1 step.

Example 2: ``text Input: x = 5, y = 5 Output: 4 Explanation: [0, 0] -> [2, 1] -> [4, 2] -> [3, 4] -> [5, 5] in 4 steps.

---

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

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Apply quadrant symmetry reduction to shrink search domains by 75%.
  • Determine safe bounding box margins for knight movement.
  • Implement level-order BFS for unweighted shortest path.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Minimum moves on an infinite 2D grid
  • Shortest path with uniform edge weights = 1
  • Symmetric coordinate movements (Knight's L-shape jumps)

Algorithmic Decision Tree:

  • Always take absolute values: x = abs(x); y = abs(y);.
  • Apply BFS level-by-level.
  • Prune paths where coordinates exceed reasonable bounds nr >= -2 && nc >= -2 && nr <= x + 2 && nc <= y + 2.

Connected Patterns:

Word LadderShortest Path in Binary MatrixRotting Oranges

1. Unbounded Standard BFS

Intuition

Queue states (r, c) starting at (0, 0). At each step, expand all 8 knight moves. Mark visited coordinates in a hash set. The first time (x, y) is popped from the queue, return the current step count.

Algorithm

  1. If x == 0 && y == 0, return 0.
  2. Initialize queue with (0, 0) and visited set containing (0,0).
  3. steps = 0.
  4. While queue is not empty:
  5. levelSize = queue.size.
  6. Loop levelSize times:
  7. Pop (r, c).
  8. If r == x && c == y, return steps.
  9. For 8 moves (dr, dc):
  10. nr = r + dr, nc = c + dc.
  11. If '(nr, nc)' not visited:
  12. Mark visited and push to queue.
  13. steps++.
  14. Return steps.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <unordered_set>
5#include <string>
6
7class Solution {
8public:
9 int minKnightMoves(int x, int y) {
10 if (x == 0 && y == 0) return 0;
11
12 std::queue<std::pair<int, int>> q;
13 std::unordered_set<std::string> visited;
14
15 q.push({0, 0});
16 visited.insert("0,0");
17
18 int dr[] = {-2, -2, -1, -1, 1, 1, 2, 2};
19 int dc[] = {-1, 1, -2, 2, -2, 2, -1, 1};
20 int steps = 0;
21
22 while (!q.empty()) {
23 int sz = q.size();
24 for (int i = 0; i < sz; ++i) {
25 auto [r, c] = q.front();
26 q.pop();
27
28 if (r == x && c == y) return steps;
29
30 for (int k = 0; k < 8; ++k) {
31 int nr = r + dr[k], nc = c + dc[k];
32 std::string key = std::to_string(nr) + "," + std::to_string(nc);
33 if (!visited.count(key)) {
34 visited.insert(key);
35 q.push({nr, nc});
36 }
37 }
38 }
39 steps++;
40 }
41 return steps;
42 }
43};
44
45int main() {
46 Solution sol;
47 std::cout << "Unbounded BFS (2, 1): " << sol.minKnightMoves(2, 1) << " (Expected: 1)\n";
48 return 0;
49}

Time & Space Complexity

  • Time complexity: O(8^d)
  • Space complexity: O(8^d)

2. Bidirectional BFS

Intuition

Instead of searching outward from (0, 0) up to radius d (exploring O(bd) nodes), Bidirectional BFS explores two spheres of radius d/2 from the start and goal. The search terminates as soon as a cell visited by the start frontier is touched by the goal frontier.

Algorithm

  1. Normalize x = abs(x), y = abs(y).
  2. If x == 0 && y == 0, return 0.
  3. Initialize qStart with (0, 0) and qEnd with (x, y).
  4. Maintain distStart and distEnd maps.
  5. Alternatingly expand the smaller frontier by one level.
  6. When an expanded neighbor is found in the opposite frontier's map, return distStart[node] + distEnd[node].
  7. Increment step counts accordingly.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <unordered_map>
5#include <cmath>
6
7class Solution {
8public:
9 int minKnightMoves(int x, int y) {
10 x = std::abs(x);
11 y = std::abs(y);
12 if (x == 0 && y == 0) return 0;
13
14 std::queue<std::pair<int, int>> qStart, qEnd;
15 std::unordered_map<int, int> distStart, distEnd;
16
17 auto hash = [](int r, int c) { return (r + 400) * 1000 + (c + 400); };
18
19 qStart.push({0, 0});
20 distStart[hash(0, 0)] = 0;
21
22 qEnd.push({x, y});
23 distEnd[hash(x, y)] = 0;
24
25 int dr[] = {-2, -2, -1, -1, 1, 1, 2, 2};
26 int dc[] = {-1, 1, -2, 2, -2, 2, -1, 1};
27
28 while (!qStart.empty() && !qEnd.empty()) {
29 // Expand start queue
30 int sz = qStart.size();
31 for (int i = 0; i < sz; ++i) {
32 auto [r, c] = qStart.front();
33 qStart.pop();
34 int d = distStart[hash(r, c)];
35
36 if (distEnd.count(hash(r, c))) {
37 return d + distEnd[hash(r, c)];
38 }
39
40 for (int k = 0; k < 8; ++k) {
41 int nr = r + dr[k], nc = c + dc[k];
42 if (nr >= -2 && nc >= -2 && nr <= x + 2 && nc <= y + 2) {
43 int h = hash(nr, nc);
44 if (!distStart.count(h)) {
45 distStart[h] = d + 1;
46 qStart.push({nr, nc});
47 }
48 }
49 }
50 }
51
52 // Expand end queue
53 sz = qEnd.size();
54 for (int i = 0; i < sz; ++i) {
55 auto [r, c] = qEnd.front();
56 qEnd.pop();
57 int d = distEnd[hash(r, c)];
58
59 if (distStart.count(hash(r, c))) {
60 return d + distStart[hash(r, c)];
61 }
62
63 for (int k = 0; k < 8; ++k) {
64 int nr = r + dr[k], nc = c + dc[k];
65 if (nr >= -2 && nc >= -2 && nr <= x + 2 && nc <= y + 2) {
66 int h = hash(nr, nc);
67 if (!distEnd.count(h)) {
68 distEnd[h] = d + 1;
69 qEnd.push({nr, nc});
70 }
71 }
72 }
73 }
74 }
75 return -1;
76 }
77};
78
79int main() {
80 Solution sol;
81 std::cout << "Bidirectional BFS (5, 5): " << sol.minKnightMoves(5, 5) << " (Expected: 4)\n";
82 return 0;
83}

Time & Space Complexity

  • Time complexity: O(b^(d/2))
  • Space complexity: O(b^(d/2))

3. First Quadrant Symmetry Bounded BFS (Optimal)

Intuition

The cleanest, fastest, and most standard interview approach. An infinite board has identical symmetry across all 4 quadrants: f(x, y) = f(|x|, |y|). By taking absolute values, we only need to search the first quadrant. To allow the knight to take its necessary 'backward dip' to reach (1, 1), we permit coordinates as low as -2. Bounding coordinates to [-2, x + 2] keeps the search region tightly confined to O(|x| * |y|) cells.

Algorithm

  1. Normalize x = abs(x), y = abs(y).
  2. If x == 0 && y == 0, return 0.
  3. Initialize queue with (0, 0) and visited set with (0, 0).
  4. steps = 0.
  5. While queue is not empty:
  6. levelSize = queue.size.
  7. Loop levelSize times:
  8. Pop (r, c).
  9. If r == x && c == y, return steps.
  10. For each of the 8 knight moves:
  11. nr = r + dr, nc = c + dc.
  12. If nr >= -2 && nc >= -2 && nr <= x + 2 && nc <= y + 2:
  13. If (nr, nc) is unvisited:
  14. Mark visited and push to queue.
  15. steps++.
  16. Return steps.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <unordered_set>
5#include <cmath>
6
7class Solution {
8public:
9 int minKnightMoves(int x, int y) {
10 x = std::abs(x);
11 y = std::abs(y);
12 if (x == 0 && y == 0) return 0;
13
14 std::queue<std::pair<int, int>> q;
15 std::unordered_set<int> visited;
16
17 auto hash = [](int r, int c) { return (r + 400) * 1000 + (c + 400); };
18
19 q.push({0, 0});
20 visited.insert(hash(0, 0));
21
22 int dr[] = {-2, -2, -1, -1, 1, 1, 2, 2};
23 int dc[] = {-1, 1, -2, 2, -2, 2, -1, 1};
24 int steps = 0;
25
26 while (!q.empty()) {
27 int sz = q.size();
28 for (int i = 0; i < sz; ++i) {
29 auto [r, c] = q.front();
30 q.pop();
31
32 if (r == x && c == y) return steps;
33
34 for (int k = 0; k < 8; ++k) {
35 int nr = r + dr[k], nc = c + dc[k];
36 // Prune search space to 1st quadrant with -2 safety margin
37 if (nr >= -2 && nc >= -2 && nr <= x + 2 && nc <= y + 2) {
38 int h = hash(nr, nc);
39 if (!visited.count(h)) {
40 visited.insert(h);
41 q.push({nr, nc});
42 }
43 }
44 }
45 }
46 steps++;
47 }
48 return steps;
49 }
50};
51
52int main() {
53 Solution sol;
54 std::cout << "Optimal BFS (5, 5): " << sol.minKnightMoves(5, 5) << " (Expected: 4)\n";
55 std::cout << "Optimal BFS (2, 1): " << sol.minKnightMoves(2, 1) << " (Expected: 1)\n";
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(|x| * |y|)
  • Space complexity: O(|x| * |y|)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Unbounded Standard BFSO(8^d)O(8^d)Expands in all 4 quadrants without symmetry normalization.Full 360-degree outward expansion
2.Bidirectional BFSO(b^(d/2))O(b^(d/2))Expands two frontiers simultaneously from (0, 0) and (x, y).Dual frontier maintenance
3.First Quadrant Symmetry Bounded BFSOptimalO(|x| * |y|)O(|x| * |y|)Normalizes to absolute coordinates and prunes search space to [-2, x + 2] x [-2, y + 2].Queue expansion

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Pruning coordinates at 0 (nr >= 0 && nc >= 0), which causes wrong answer for (1, 1).

Pitfall 2:

Not taking absolute values of x and y, searching all 4 quadrants unnecessarily.

Pitfall 3:

Using DFS, which gets stuck in infinite loops on an infinite chess board.

Crucial Edge Cases to Validate:

  • Starting square (x = 0, y = 0) — Returns 0 steps immediately.
  • Neighboring diagonal (x = 1, y = 1) — Requires 2 steps: (0,0) -> (2, -1) -> (1, 1); handled by the -2 boundary margin.
  • Single knight jump (e.g. x = 2, y = 1 or x = 1, y = 2) — Returns 1 step immediately on level 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the symmetry reduction immediately: 'Since the board and knight moves are symmetric across both axes, minKnightMoves(x, y) = minKnightMoves(|x|, |y|).'
  2. Explain the boundary condition: 'We must allow small negative coordinates (-2) to permit the knight to swing backward for close targets like (1, 1).'
  3. Mention that upper bounds can be safely capped at x + 2 and y + 2.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why can we set x = abs(x) and y = abs(y) without changing the minimum number of knight moves?

2.Why is a negative lower bound (e.g. nr >= -2, nc >= -2) strictly necessary instead of pruning at nr >= 0, nc >= 0?

3.Why is BFS guaranteed to find the MINIMUM moves?

Back to DSA Sheet