Skip to main content
Talentd

Minimum Knight Moves - Solution & Explanation

MediumPremiumFree on FleetCodeBreadth-First Search16 min readAsked at: Amazon, Microsoft, Apple +10
Practice this problem

Problem Statement

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:

  1. Create two queues, q1 and q2, for "start -> end" and "end -> start" search directions, respectively.
  2. Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps).
  3. 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.
  4. 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.

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
BFS—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First SearchO((|x|+|y|)^2)O((|x|+|y|)^2)General shortest-path solution on the infinite board
Optimized BFS with Symmetry PruningO((|x|+|y|)^2)O((|x|+|y|)^2)Preferred approach in interviews; reduces search space using symmetry

Video Solution

Steps by Knight GFG Solution | BFS | Leetcode Minimum knight moves | Complete Graph Playlist • Hello World • 26,657 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Knight Moves with our built-in code editor and test cases.

Practice on FleetCode
Previous

Check Knight Tour Configuration