1197. Minimum Knight Moves - Solution

The 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.

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

Approach overview

Problem Overview: You start with a knight at (0,0) on an infinite chessboard. The task is to reach a target coordinate (x, y) using the minimum number of knight moves. Each move follows the classic L-shape pattern: two steps in one direction and one step perpendicular.

Approach 1: Breadth-First Search (Shortest Path) (Time: O((|x|+|y|)^2), Space: O((|x|+|y|)^2))

This problem is a shortest path search on an implicit graph. Each board coordinate represents a node, and the 8 possible knight moves form edges. Breadth-First Search works perfectly because every move has equal cost. Start from (0,0), push it into a queue, and explore all valid knight moves level by level. Use a visited set to avoid revisiting coordinates.

The key observation: the board is symmetric around both axes. You can convert the target to the first quadrant using x = abs(x) and y = abs(y). This drastically reduces the search space. During BFS, limit exploration to coordinates slightly beyond the target (commonly >= -2). This prevents the queue from expanding infinitely while still preserving correctness. The first time you dequeue the target coordinate, the level count equals the minimum number of moves.

This approach models the board as an unweighted graph and computes the shortest path using standard BFS traversal. The search region grows roughly proportional to the Manhattan distance from the origin.

Approach 2: Optimized BFS with Symmetry Pruning (Time: O((|x|+|y|)^2), Space: O((|x|+|y|)^2))

The default optimized solution still uses BFS but aggressively prunes the search space using geometric symmetry. Because knight movement is symmetric across both axes and diagonals, convert the target to the first quadrant and only explore positions where x >= -2 and y >= -2. Positions further negative never contribute to the optimal path.

Each BFS step generates the eight possible knight moves and pushes unseen positions into the queue. The pruning rule prevents unnecessary exploration in distant directions. In practice this reduces the state space dramatically, making the algorithm fast even for large coordinates like (300, 300). The algorithm still guarantees correctness because the shortest path never requires moving far away from the target direction.

This technique combines BFS traversal with symmetry reduction, a common optimization for grid and graph search problems.

Recommended for interviews: BFS with symmetry pruning. Interviewers expect you to recognize the problem as an unweighted shortest-path search and apply BFS. Mentioning symmetry (abs(x), abs(y)) and bounding the search to avoid infinite expansion demonstrates deeper algorithmic thinking. A plain BFS shows understanding, but the pruned BFS shows strong problem-solving skills.

Approach 1: BFS

This problem can be solved using the BFS shortest path model. The search space for this problem is not large, so we can directly use the naive BFS. The solution below also provides the code for bidirectional BFS for reference.

Bidirectional BFS is a common optimization method for BFS. The main implementation ideas are as follows:

Create two queues, q1 and q2, for "start -> end" and "end -> start" search directions, respectively.
Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps).
During each search, prioritize the queue with fewer elements for search expansion. If a node visited from the other direction is found during the expansion, it means the shortest path has been found.
If one of the queues is empty, it means that the search in the current direction cannot continue, indicating that the start and end points are not connected, and there is no need to continue the search.

Python

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        q = deque([(0, 0)])
        ans = 0
        vis = {(0, 0)}
        dirs = ((-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1))
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                if (i, j) == (x, y):
                    return ans
                for a, b in dirs:
                    c, d = i + a, j + b
                    if (c, d) not in vis:
                        vis.add((c, d))
                        q.append((c, d))
            ans += 1
        return -1

Java

class Solution {
    public int minKnightMoves(int x, int y) {
        x += 310;
        y += 310;
        int ans = 0;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {310, 310});
        boolean[][] vis = new boolean[700][700];
        vis[310][310] = true;
        int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
        while (!q.isEmpty()) {
            for (int k = q.size(); k > 0; --k) {
                int[] p = q.poll();
                if (p[0] == x && p[1] == y) {
                    return ans;
                }
                for (int[] dir : dirs) {
                    int c = p[0] + dir[0];
                    int d = p[1] + dir[1];
                    if (!vis[c][d]) {
                        vis[c][d] = true;
                        q.offer(new int[] {c, d});
                    }
                }
            }
            ++ans;
        }
        return -1;
    }
}

C++

class Solution {
public:
    int minKnightMoves(int x, int y) {
        x += 310;
        y += 310;
        int ans = 0;
        queue<pair<int, int>> q;
        q.push({310, 310});
        vector<vector<bool>> vis(700, vector<bool>(700));
        vis[310][310] = true;
        vector<vector<int>> dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
        while (!q.empty()) {
            for (int k = q.size(); k > 0; --k) {
                auto p = q.front();
                q.pop();
                if (p.first == x && p.second == y) return ans;
                for (auto& dir : dirs) {
                    int c = p.first + dir[0], d = p.second + dir[1];
                    if (!vis[c][d]) {
                        vis[c][d] = true;
                        q.push({c, d});
                    }
                }
            }
            ++ans;
        }
        return -1;
    }
};

func minKnightMoves(x int, y int) int {
	x, y = x+310, y+310
	ans := 0
	q := [][]int{{310, 310}}
	vis := make([][]bool, 700)
	for i := range vis {
		vis[i] = make([]bool, 700)
	}
	dirs := [][]int{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}
	for len(q) > 0 {
		for k := len(q); k > 0; k-- {
			p := q[0]
			q = q[1:]
			if p[0] == x && p[1] == y {
				return ans
			}
			for _, dir := range dirs {
				c, d := p[0]+dir[0], p[1]+dir[1]
				if !vis[c][d] {
					vis[c][d] = true
					q = append(q, []int{c, d})
				}
			}
		}
		ans++
	}
	return -1
}

Rust

use std::collections::VecDeque;

const DIR: [(i32, i32); 8] = [
    (-2, 1),
    (2, 1),
    (-1, 2),
    (1, 2),
    (2, -1),
    (-2, -1),
    (1, -2),
    (-1, -2),
];

impl Solution {
    #[allow(dead_code)]
    pub fn min_knight_moves(x: i32, y: i32) -> i32 {
        // The original x, y are from [-300, 300]
        // Let's shift them to [0, 600]
        let x: i32 = x + 300;
        let y: i32 = y + 300;
        let mut ret = -1;
        let mut vis: Vec<Vec<bool>> = vec![vec![false; 618]; 618];
        // <X, Y, Current Steps>
        let mut q: VecDeque<(i32, i32, i32)> = VecDeque::new();

        q.push_back((300, 300, 0));

        while !q.is_empty() {
            let (i, j, s) = q.front().unwrap().clone();
            q.pop_front();
            if i == x && j == y {
                ret = s;
                break;
            }
            Self::enqueue(&mut vis, &mut q, i, j, s);
        }

        ret
    }

    #[allow(dead_code)]
    fn enqueue(
        vis: &mut Vec<Vec<bool>>,
        q: &mut VecDeque<(i32, i32, i32)>,
        i: i32,
        j: i32,
        cur_step: i32,
    ) {
        let next_step = cur_step + 1;
        for (dx, dy) in DIR {
            let x = i + dx;
            let y = j + dy;
            if Self::check_bounds(x, y) || vis[x as usize][y as usize] {
                // This <X, Y> pair is either out of bound, or has been visited before
                // Just ignore this pair
                continue;
            }
            // Otherwise, add the pair to the queue
            // Also remember to update the vis vector
            vis[x as usize][y as usize] = true;
            q.push_back((x, y, next_step));
        }
    }

    #[allow(dead_code)]
    fn check_bounds(i: i32, j: i32) -> bool {
        i < 0 || i > 600 || j < 0 || j > 600
    }
}

Try this approach in the editor

Approach 2: Default Approach

Python

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        def extend(m1, m2, q):
            for _ in range(len(q)):
                i, j = q.popleft()
                step = m1[(i, j)]
                for a, b in (
                    (-2, 1),
                    (-1, 2),
                    (1, 2),
                    (2, 1),
                    (2, -1),
                    (1, -2),
                    (-1, -2),
                    (-2, -1),
                ):
                    x, y = i + a, j + b
                    if (x, y) in m1:
                        continue
                    if (x, y) in m2:
                        return step + 1 + m2[(x, y)]
                    q.append((x, y))
                    m1[(x, y)] = step + 1
            return -1

        if (x, y) == (0, 0):
            return 0
        q1, q2 = deque([(0, 0)]), deque([(x, y)])
        m1, m2 = {(0, 0): 0}, {(x, y): 0}
        while q1 and q2:
            t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2)
            if t != -1:
                return t
        return -1

Java

class Solution {
    private int n = 700;

    public int minKnightMoves(int x, int y) {
        if (x == 0 && y == 0) {
            return 0;
        }
        x += 310;
        y += 310;
        Map<Integer, Integer> m1 = new HashMap<>();
        Map<Integer, Integer> m2 = new HashMap<>();
        m1.put(310 * n + 310, 0);
        m2.put(x * n + y, 0);
        Queue<int[]> q1 = new ArrayDeque<>();
        Queue<int[]> q2 = new ArrayDeque<>();
        q1.offer(new int[] {310, 310});
        q2.offer(new int[] {x, y});
        while (!q1.isEmpty() && !q2.isEmpty()) {
            int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
            if (t != -1) {
                return t;
            }
        }
        return -1;
    }

    private int extend(Map<Integer, Integer> m1, Map<Integer, Integer> m2, Queue<int[]> q) {
        int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
        for (int k = q.size(); k > 0; --k) {
            int[] p = q.poll();
            int step = m1.get(p[0] * n + p[1]);
            for (int[] dir : dirs) {
                int x = p[0] + dir[0];
                int y = p[1] + dir[1];
                if (m1.containsKey(x * n + y)) {
                    continue;
                }
                if (m2.containsKey(x * n + y)) {
                    return step + 1 + m2.get(x * n + y);
                }
                m1.put(x * n + y, step + 1);
                q.offer(new int[] {x, y});
            }
        }
        return -1;
    }
}

C++

typedef pair<int, int> PII;

class Solution {
public:
    int n = 700;

    int minKnightMoves(int x, int y) {
        if (x == 0 && y == 0) return 0;
        x += 310;
        y += 310;
        unordered_map<int, int> m1;
        unordered_map<int, int> m2;
        m1[310 * n + 310] = 0;
        m2[x * n + y] = 0;
        queue<PII> q1;
        queue<PII> q2;
        q1.push({310, 310});
        q2.push({x, y});
        while (!q1.empty() && !q2.empty()) {
            int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2);
            if (t != -1) return t;
        }
        return -1;
    }

    int extend(unordered_map<int, int>& m1, unordered_map<int, int>& m2, queue<PII>& q) {
        vector<vector<int>> dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
        for (int k = q.size(); k > 0; --k) {
            auto p = q.front();
            q.pop();
            int i = p.first, j = p.second;
            int step = m1[i * n + j];
            for (auto& dir : dirs) {
                int x = i + dir[0], y = j + dir[1];
                if (m1.count(x * n + y)) continue;
                if (m2.count(x * n + y)) return step + 1 + m2[x * n + y];
                m1[x * n + y] = step + 1;
                q.push({x, y});
            }
        }
        return -1;
    }
};

func minKnightMoves(x int, y int) int {
	if x == 0 && y == 0 {
		return 0
	}
	n := 700
	x, y = x+310, y+310
	q1, q2 := []int{310*700 + 310}, []int{x*n + y}
	m1, m2 := map[int]int{310*700 + 310: 0}, map[int]int{x*n + y: 0}
	dirs := [][]int{{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}}
	extend := func() int {
		for k := len(q1); k > 0; k-- {
			p := q1[0]
			q1 = q1[1:]
			i, j := p/n, p%n
			step := m1[i*n+j]
			for _, dir := range dirs {
				x, y := i+dir[0], j+dir[1]
				t := x*n + y
				if _, ok := m1[t]; ok {
					continue
				}
				if v, ok := m2[t]; ok {
					return step + 1 + v
				}
				m1[t] = step + 1
				q1 = append(q1, t)
			}
		}
		return -1
	}
	for len(q1) > 0 && len(q2) > 0 {
		if len(q1) <= len(q2) {
			q1, q2 = q2, q1
			m1, m2 = m2, m1
		}
		t := extend()
		if t != -1 {
			return t
		}
	}
	return -1
}

Rust

use std::collections::HashMap;
use std::collections::VecDeque;

const DIR: [(i32, i32); 8] = [
    (-2, 1),
    (2, 1),
    (-1, 2),
    (1, 2),
    (2, -1),
    (-2, -1),
    (1, -2),
    (-1, -2),
];

impl Solution {
    #[allow(dead_code)]
    pub fn min_knight_moves(x: i32, y: i32) -> i32 {
        if x == 0 && y == 0 {
            return 0;
        }
        // Otherwise, let's shift <X, Y> from [-300, 300] -> [0, 600]
        let x = x + 300;
        let y = y + 300;
        let mut ret = -1;
        // Initialize the two hash map, used to track if a node has been visited
        let mut map_to: HashMap<i32, i32> = HashMap::new();
        let mut map_from: HashMap<i32, i32> = HashMap::new();
        // Input the original status
        map_to.insert(601 * 300 + 300, 0);
        map_from.insert(601 * x + y, 0);
        let mut q_to: VecDeque<(i32, i32)> = VecDeque::new();
        let mut q_from: VecDeque<(i32, i32)> = VecDeque::new();
        // Initialize the two queue
        q_to.push_back((300, 300));
        q_from.push_back((x, y));

        while !q_to.is_empty() && !q_from.is_empty() {
            let step = if q_to.len() < q_from.len() {
                Self::extend(&mut map_to, &mut map_from, &mut q_to)
            } else {
                Self::extend(&mut map_from, &mut map_to, &mut q_from)
            };
            if step != -1 {
                ret = step;
                break;
            }
        }

        ret
    }

    #[allow(dead_code)]
    fn extend(
        map_to: &mut HashMap<i32, i32>,
        map_from: &mut HashMap<i32, i32>,
        cur_q: &mut VecDeque<(i32, i32)>,
    ) -> i32 {
        let n = cur_q.len();
        for _ in 0..n {
            let (i, j) = cur_q.front().unwrap().clone();
            cur_q.pop_front();
            // The cur_step here must exist
            let cur_step = map_to.get(&(601 * i + j)).unwrap().clone();
            for (dx, dy) in DIR {
                let x = i + dx;
                let y = j + dy;
                // Check if this node has been visited
                if map_to.contains_key(&(601 * x + y)) {
                    // Just ignore this node
                    continue;
                }
                // Check if this node has been visited by the other side
                if map_from.contains_key(&(601 * x + y)) {
                    // We found the node
                    return (cur_step + 1 + map_from.get(&(601 * x + y)).unwrap().clone());
                }
                // Otherwise, update map_to and push the new node to queue
                map_to.insert(601 * x + y, cur_step + 1);
                cur_q.push_back((x, y));
            }
        }
        -1
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
BFS	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Breadth-First Search	O((\|x\|+\|y\|)^2)	O((\|x\|+\|y\|)^2)	General shortest-path solution on the infinite board
Optimized BFS with Symmetry Pruning	O((\|x\|+\|y\|)^2)	O((\|x\|+\|y\|)^2)	Preferred approach in interviews; reduces search space using symmetry

Frequently asked questions

Is Minimum Knight Moves easy or hard?

Minimum Knight Moves is generally classified as a Medium problem. The BFS idea is straightforward, but handling the infinite board and recognizing symmetry optimizations makes it slightly more challenging than a basic grid traversal problem.

Minimum Knight Moves Python/Java solution

Most implementations use BFS with a queue and a visited set. Python solutions typically use collections.deque, while Java solutions use a Queue with LinkedList or ArrayDeque. Both follow the same logic: push (0,0), generate the 8 knight moves, track visited cells, and stop when the target coordinate is reached.

How to solve Minimum Knight Moves in O(n)?

The problem cannot be solved in strict O(n) time because the search area grows in two dimensions. The optimal practical approach is BFS with symmetry reduction, which limits exploration to a region proportional to (|x|+|y|)^2. This guarantees the shortest path while keeping the search manageable.

What is the best approach for Minimum Knight Moves?

Breadth-First Search (BFS) is the best approach because the problem asks for the minimum number of moves, which is a shortest path in an unweighted graph. Starting from (0,0), BFS explores all positions level by level until the target (x,y) is reached. With symmetry optimization (using abs(x), abs(y)), the search space becomes much smaller while maintaining O((|x|+|y|)^2) time complexity.

Is Minimum Knight Moves asked at Google/Amazon/Meta?

Minimum Knight Moves is a common interview-style graph problem and has appeared in interviews at companies like Google and Amazon. It tests your ability to model grid movement as a graph and apply BFS to compute the shortest path.

What data structure is used in Minimum Knight Moves?

The main data structures are a queue for BFS traversal and a hash set (or visited matrix) to track explored coordinates. The queue processes positions level by level, while the visited set prevents revisiting the same coordinate.

What is the time complexity of Minimum Knight Moves?

The BFS solution runs in O((|x|+|y|)^2) time because the algorithm explores a bounded region around the target coordinates. Each position generates up to 8 knight moves, and each coordinate is visited at most once. Space complexity is also O((|x|+|y|)^2) due to the queue and visited set.

Minimum Knight Moves solution and explanation

The problem

Approach overview

Approach 1: BFS

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Knight Moves solution and explanation

The problem

Approach overview

Approach 1: BFS

Approach 2: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems