Minimum Knight Moves

How it works

Due to the knight's movement symmetry, we only need to consider the first quadrant (positive x and y). The minimum moves to reach (-x, y), (x, -y), or (-x, -y) are the same as reaching (x, y).

We can define a recursive relation: the minimum moves to reach (x, y) equals 1 plus the minimum of reaching (|x-1|, |y-2|) or (|x-2|, |y-1|). The absolute values keep us in the first quadrant, and memoization prevents redundant calculations.

Steps

1. Take absolute values of x and y to work in the first quadrant.
2. Define base cases: (0, 0) requires 0 moves; positions where x+y = 2 require 2 moves.
3. For other positions, recursively compute: min(dfs(|x-1|, |y-2|), dfs(|x-2|, |y-1|)) + 1.
4. Use memoization to cache results for each (x, y) pair.
5. Return the computed minimum moves.

Complexity

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

Where (x,y) is the coordinate of the target.

Things to watch for

Not Exploiting Symmetry to Reduce Search Space

The knight's movement is symmetric across both axes. Searching the entire coordinate plane when only the first quadrant (using absolute values of x and y) is necessary wastes time and memory. Always convert to positive coordinates first.

Unbounded BFS Without Coordinate Limits

Without restricting the search area, BFS can explore positions far from both origin and target, leading to memory exhaustion. The optimal path rarely strays far beyond the target coordinates, so limiting exploration to a reasonable bounding box improves efficiency.

Missing Base Cases in Memoized DFS

The recursive solution requires proper base cases. The position (0, 0) needs 0 moves, and positions where x + y = 2 (like (1, 1), (2, 0), (0, 2)) need exactly 2 moves. Missing these base cases causes infinite recursion or incorrect results.

from functools import lru_cache

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:

        @lru_cache(maxsize=None)
        def dfs(x, y):
            if x + y == 0:
                # base case: (0, 0)
                return 0
            elif x + y == 2:
                # base case: (1, 1), (0, 2), (2, 0)
                return 2
            else:
                return min(dfs(abs(x - 1), abs(y - 2)), dfs(abs(x - 2), abs(y - 1))) + 1

        return dfs(abs(x), abs(y))

class Solution {
private:
    unordered_map<string, int> memo;

    int dfs(int x, int y) {
        string key = to_string(x) + "," + to_string(y);
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

        if (x + y == 0) {
            return 0;
        } else if (x + y == 2) {
            return 2;
        } else {
            int ret = min(dfs(abs(x - 1), abs(y - 2)),
                         dfs(abs(x - 2), abs(y - 1))) + 1;
            memo[key] = ret;
            return ret;
        }
    }

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