DSA problem
Minimum Knight Moves
In an infinite chess board with coordinates from -infinity to +infinity, a knight starts at the square (0, 0) and wants to reach the square (x, y). A knight can move to any of 8 L-shaped squares relative to its current position: (+/-1, +/-2) and (+/-2, +/-1). Return the minimum number of moves to reach (x, y).
Because every move costs the same (one), the shortest path on this infinite grid is exactly the BFS distance. The complication is that the board is unbounded, so we must shrink the search space.
Two symmetries help. First, the knight's move pattern is invariant under reflection across both axes, so the minimum number of moves from (0, 0) to (x, y) equals the minimum from (0, 0) to (|x|, |y|). We can take absolute values up front and only search the first quadrant.
Second, we never need to wander far into negative coordinates, but the knight may briefly visit (-1, -1) or (-2, -2) near the origin on optimal paths to small targets, so we keep a small negative buffer when restricting the search to non-negative coordinates. With this, BFS visits O((x + y)^2) cells in the worst case and uses a hash set for visited squares, giving an overall O(max(x, y)^2) time and space.
Examples
x = 2, y = 11x = 5, y = 54x = 0, y = 00Constraints
- -300 <= x, y <= 300
- 0 <= |x| + |y| <= 300
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.