Minimum Knight Moves
Medium · Graphs · Breadth-First Search
Problem
A knight stands on square [0, 0] of a chessboard that is infinite in every direction. In one move it jumps two squares along one axis and one square along the other, so from [a, b] it can reach eight squares such as [a + 1, b + 2] or [a - 2, b - 1].
Return the minimum number of moves the knight needs to reach square [x, y]. Every square can be reached.
Examples
Input: x = 2, y = 1 Output: 1
One jump: two along x, one along y.
Input: x = 5, y = 5 Output: 4
[0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5].
Input: x = 1, y = 0 Output: 3
The square right next to the start is surprisingly far: no single jump or pair of jumps lands there.
Constraints
- -300 <= x, y <= 300
- 0 <= |x| + |y| <= 300
Approaches
- Breadth-first search in one quadrant — time O(|x| · |y|), space O(|x| · |y|)
Follow-up
Bidirectional search halves the radius each side explores: grow one frontier from [0, 0] and one from the target and stop when they meet. On a finite board with obstacles the symmetry and the closed form no longer hold, but plain breadth-first search still does.
Related problems
Start free on Cariara · Coding problems · System design studio
