Minimum Knight Moves

Problem

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.

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
• 0 <= |x| + |y| <= 300

Solution

Method 1 – Breadth-First Search (BFS)

Intuition

The knight moves symmetrically, so we can always solve for the first quadrant and use BFS to find the shortest path. BFS explores all possible moves level by level and guarantees the minimum steps.

Approach

1. Take absolute values of x and y (due to symmetry).
2. Use BFS starting from (0,0), with a queue and a visited set.
3. For each position, try all 8 possible knight moves.
4. Stop when reaching (x, y) and return the number of steps.
5. Use a reasonable bound (e.g., x+3, y+3) to limit the search space.

Code

C++

class Solution {
public:
    int minKnightMoves(int x, int y) {
        x = abs(x); y = abs(y);
        vector<pair<int,int>> dirs = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
        queue<pair<int,int>> q;
        set<pair<int,int>> vis;
        q.push({0,0});
        vis.insert({0,0});
        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [cx, cy] = q.front(); q.pop();
                if (cx == x && cy == y) return steps;
                for (auto& d : dirs) {
                    int nx = cx + d.first, ny = cy + d.second;
                    if (nx >= -2 && ny >= -2 && nx <= x+2 && ny <= y+2 && !vis.count({nx,ny})) {
                        vis.insert({nx,ny});
                        q.push({nx,ny});
                    }
                }
            }
            ++steps;
        }
        return -1;
    }
};

Go

func minKnightMoves(x int, y int) int {
    x, y = abs(x), abs(y)
    dirs := [8][2]int{{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}}
    type state struct{ x, y int }
    q := []state{{0,0}}
    vis := map[state]struct{}{{0,0}: {}}
    steps := 0
    for len(q) > 0 {
        nq := []state{}
        for _, s := range q {
            if s.x == x && s.y == y { return steps }
            for _, d := range dirs {
                nx, ny := s.x+d[0], s.y+d[1]
                ns := state{nx,ny}
                if nx >= -2 && ny >= -2 && nx <= x+2 && ny <= y+2 {
                    if _, ok := vis[ns]; !ok {
                        vis[ns] = struct{}{}
                        nq = append(nq, ns)
                    }
                }
            }
        }
        q = nq
        steps++
    }
    return -1
}
func abs(a int) int { if a < 0 { return -a }; return a }

Java

class Solution {
    public int minKnightMoves(int x, int y) {
        x = Math.abs(x); y = Math.abs(y);
        int[][] dirs = {{1,2},{2,1},{-1,2},{-2,1},{1,-2},{2,-1},{-1,-2},{-2,-1}};
        Queue<int[]> q = new LinkedList<>();
        Set<String> vis = new HashSet<>();
        q.offer(new int[]{0,0});
        vis.add("0,0");
        int steps = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                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];
                    String key = nx+","+ny;
                    if (nx >= -2 && ny >= -2 && nx <= x+2 && ny <= y+2 && !vis.contains(key)) {
                        vis.add(key);
                        q.offer(new int[]{nx,ny});
                    }
                }
            }
            steps++;
        }
        return -1;
    }
}

Kotlin

class Solution {
    fun minKnightMoves(x: Int, y: Int): Int {
        val tx = Math.abs(x)
        val ty = Math.abs(y)
        val dirs = arrayOf(
            intArrayOf(1,2), intArrayOf(2,1), intArrayOf(-1,2), intArrayOf(-2,1),
            intArrayOf(1,-2), intArrayOf(2,-1), intArrayOf(-1,-2), intArrayOf(-2,-1)
        )
        val vis = mutableSetOf<Pair<Int,Int>>()
        val q = ArrayDeque<Pair<Int,Int>>()
        q.add(0 to 0)
        vis.add(0 to 0)
        var steps = 0
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val (cx, cy) = q.removeFirst()
                if (cx == tx && cy == ty) return steps
                for ((dx, dy) in dirs) {
                    val nx = cx + dx
                    val ny = cy + dy
                    if (nx >= -2 && ny >= -2 && nx <= tx+2 && ny <= ty+2 && vis.add(nx to ny)) {
                        q.add(nx to ny)
                    }
                }
            }
            steps++
        }
        return -1
    }
}

Python

def min_knight_moves(x: int, y: int) -> int:
    from collections import deque
    x, y = abs(x), abs(y)
    dirs = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)]
    q = deque([(0,0)])
    vis = set([(0,0)])
    steps = 0
    while q:
        for _ in range(len(q)):
            cx, cy = q.popleft()
            if cx == x and cy == y:
                return steps
            for dx, dy in dirs:
                nx, ny = cx+dx, cy+dy
                if -2 <= nx <= x+2 and -2 <= ny <= y+2 and (nx,ny) not in vis:
                    vis.add((nx,ny))
                    q.append((nx,ny))
        steps += 1
    return -1

Rust

impl Solution {
    pub fn min_knight_moves(x: i32, y: i32) -> i32 {
        use std::collections::{HashSet, VecDeque};
        let (x, y) = (x.abs(), y.abs());
        let dirs = [(1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1)];
        let mut vis = HashSet::new();
        let mut q = VecDeque::new();
        q.push_back((0,0));
        vis.insert((0,0));
        let mut steps = 0;
        while !q.is_empty() {
            for _ in 0..q.len() {
                let (cx, cy) = q.pop_front().unwrap();
                if cx == x && cy == y { return steps; }
                for &(dx, dy) in &dirs {
                    let nx = cx + dx;
                    let ny = cy + dy;
                    if nx >= -2 && ny >= -2 && nx <= x+2 && ny <= y+2 && vis.insert((nx,ny)) {
                        q.push_back((nx,ny));
                    }
                }
            }
            steps += 1;
        }
        -1
    }
}

TypeScript

class Solution {
    minKnightMoves(x: number, y: number): number {
        x = Math.abs(x); y = Math.abs(y);
        const dirs = [[1,2],[2,1],[-1,2],[-2,1],[1,-2],[2,-1],[-1,-2],[-2,-1]];
        const vis = new Set<string>();
        const q: [number, number][] = [[0,0]];
        vis.add('0,0');
        let steps = 0;
        while (q.length) {
            const nq: [number, number][] = [];
            for (const [cx, cy] of q) {
                if (cx === x && cy === y) return steps;
                for (const [dx, dy] of dirs) {
                    const nx = cx + dx, ny = cy + dy;
                    const key = `${nx},${ny}`;
                    if (nx >= -2 && ny >= -2 && nx <= x+2 && ny <= y+2 && !vis.has(key)) {
                        vis.add(key);
                        nq.push([nx,ny]);
                    }
                }
            }
            q.length = 0;
            q.push(...nq);
            steps++;
        }
        return -1;
    }
}

Complexity

• ⏰ Time complexity: O(x*y), but bounded by the search space (usually much less due to symmetry and pruning).
• 🧺 Space complexity: O(x*y), for the visited set and queue.