Minimum Knight Moves

Medium Graphs BFS for shortest path Original on LeetCode

Minimum Knight Moves is a medium graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (symmetry + memoized recursion), runs in O(|x| · |y|) time and O(|x| · |y|) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over a bounded board) up.

Problem

A knight starts at square (0, 0) of a chessboard that stretches forever in every direction. In one jump it moves two squares along one axis and one square along the other, so it has eight possible jumps from any square.

Given the coordinates x and y of a target square, return the smallest number of jumps the knight needs to land on (x, y). It is always possible to reach the target.

Examples

Example 1

Input
x = 1, y = 2
Output
1
Why
(1, 2) is one of the eight squares a knight reaches from the origin in a single jump.

Example 2

Input
x = 4, y = 4
Output
4
Why
One shortest route is (0,0) → (2,1) → (4,2) → (2,3) → (4,4).

Example 3

Input
x = -3, y = 0
Output
3
Why
One route is (0,0) → (-2,1) → (-1,-1) → (-3,0), and no route with one or two jumps lands there.

Constraints

  • -300 <= x, y <= 300
  • 0 <= |x| + |y| <= 300
  • The board is infinite in every direction, and an answer always exists.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS over a bounded board)O(B²)O(B²)
Optimal (symmetry + memoized recursion)O(|x| · |y|)O(|x| · |y|)

1Brute force (BFS over a bounded board)

TimeO(B²)In the worst case the search touches a large part of the B × B box around the origin, where B is about 2 · 300.
SpaceO(B²)The visited grid and the queue cover the same box.

Treat each square as a node and each of the eight knight jumps as an edge. A breadth-first search from the origin reaches squares in order of jump count, so the level at which the target is popped is the answer. The search is kept inside a box a little larger than the coordinate limits so the visited array stays finite.

  1. Use a visited grid with an offset so coordinates from -OFF to OFF fit.
  2. Push (0, 0) with distance 0.
  3. Pop level by level; if the popped square is the target, return the level.
  4. Otherwise push every unvisited in-box neighbour of the eight jumps.
class Solution {
    public int minKnightMoves(int x, int y) {
        final int OFF = 310, SIZE = 2 * OFF + 1;
        int[][] dirs = {{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
        boolean[][] seen = new boolean[SIZE][SIZE];
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0, 0});
        seen[OFF][OFF] = true;
        int steps = 0;
        while (!q.isEmpty()) {
            for (int size = q.size(); size > 0; size--) {
                int[] cur = q.poll();
                if (cur[0] == x && cur[1] == y) return steps;
                for (int[] d : dirs) {
                    int nx = cur[0] + d[0], ny = cur[1] + d[1];
                    if (nx < -OFF || nx > OFF || ny < -OFF || ny > OFF) continue;
                    if (seen[nx + OFF][ny + OFF]) continue;
                    seen[nx + OFF][ny + OFF] = true;
                    q.add(new int[]{nx, ny});
                }
            }
            steps++;
        }
        return -1;
    }
}

2Optimal (symmetry + memoized recursion)

TimeO(|x| · |y|)Each recursive state is a pair of non-negative coordinates no larger than the start, and each is computed once.
SpaceO(|x| · |y|)The memo table, plus a recursion depth of about (|x| + |y|) / 3.

Because of symmetry only (|x|, |y|) matters. Working backwards from a target in the first quadrant, the useful last jumps are the two that move towards the origin: to (|x-1|, |y-2|) or (|x-2|, |y-1|) (taking absolute values folds the square back into the first quadrant). Base cases: the origin needs 0 jumps, and any square with x + y = 2, that is (2,0), (0,2) or (1,1), needs exactly 2. Memoizing the recursion visits each (x, y) pair at most once.

  1. Set x = |x|, y = |y|.
  2. f(x, y): if x + y == 0 return 0; if x + y == 2 return 2.
  3. Otherwise f(x, y) = 1 + min(f(|x-1|, |y-2|), f(|x-2|, |y-1|)), cached in a map.
class Solution {
    private final Map<Integer, Integer> memo = new HashMap<>();

    public int minKnightMoves(int x, int y) {
        return dfs(Math.abs(x), Math.abs(y));
    }

    private int dfs(int x, int y) {
        if (x + y == 0) return 0;
        if (x + y == 2) return 2;
        int key = x * 1000 + y;
        Integer cached = memo.get(key);
        if (cached != null) return cached;
        int best = 1 + Math.min(dfs(Math.abs(x - 1), Math.abs(y - 2)), dfs(Math.abs(x - 2), Math.abs(y - 1)));
        memo.put(key, best);
        return best;
    }
}

Edge cases to test

  • Target is the origin (answer 0)
  • Target (1, 1): two squares away diagonally needs 2 jumps
  • Target (1, 0) or (0, 1): a single orthogonal step needs 3 jumps
  • Negative coordinates (the board is symmetric, so only |x| and |y| matter)
  • Far targets such as (150, 150) or (300, 0)

Hints

Hint 1

Every jump costs the same, so the fewest jumps is a shortest path in an unweighted graph whose nodes are squares. Which search finds that?

Hint 2

The board is symmetric about both axes and the diagonal, so you can replace (x, y) by (|x|, |y|). The BFS never needs to wander far into negative coordinates.

Hint 3

Think backwards from the target: from (x, y) with x, y ≥ 0, a good last jump moves you two closer on one axis and one closer on the other. Memoize f(x, y) = 1 + min(f(|x-1|, |y-2|), f(|x-2|, |y-1|)), with small base cases.

FAQ

What is the best time complexity for Minimum Knight Moves?

Optimal (symmetry + memoized recursion) runs in O(|x| · |y|) time and O(|x| · |y|) extra space. Each recursive state is a pair of non-negative coordinates no larger than the start, and each is computed once.

Which pattern does Minimum Knight Moves use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Minimum Knight Moves?

Yes. Brute force (BFS over a bounded board) takes O(B²) time and O(B²) space. Treat each square as a node and each of the eight knight jumps as an edge.

Which edge cases should I test for Minimum Knight Moves?

Target is the origin (answer 0); Target (1, 1): two squares away diagonally needs 2 jumps; Target (1, 0) or (0, 1): a single orthogonal step needs 3 jumps; Negative coordinates (the board is symmetric, so only |x| and |y| matter); Far targets such as (150, 150) or (300, 0).