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.

Description Hints 3 Solution Video 19:26

1197. Minimum Knight Moves

Medium41.8% acceptance13 companiesPremium elsewhere, free here

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

Asked at 13 companies

Verily Waymo Uber Apple NVIDIA Databricks

Google Amazon Microsoft Meta Oracle LinkedIn

+1 more

Bloomberg

Topics

Breadth-First Search

Hints open one at a time

Hint 1

You can simulate the movements since the limits are low.

Hint 2

Is there a search algorithm applicable to this problem?

Hint 3

Since we want the minimum number of moves, we can use Breadth First Search.

19:26

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution