Minimum knight moves on an infinite chessboard

A knight starts at (0, 0) on an infinite chess board. Return the fewest moves it needs to reach (x, y). A knight moves two squares in one direction and one square in the perpendicular direction.

Interface

Unless you agree on a different interface with the interviewer, assume:

• min_knight_moves(x: int, y: int) -> int

Example

min_knight_moves(2, 1)  ->  1
min_knight_moves(5, 5)  ->  4
min_knight_moves(0, 0)  ->  0
min_knight_moves(1, 0)  ->  3
min_knight_moves(1, 1)  ->  2

Constraints

• |x| + |y| <= 300; an answer always exists on an infinite board.

Clarifying questions

• Is the board infinite or a fixed n x n (and then, which cells are inside)?
• Can the start be anywhere, or always the origin?
• Are there blocked squares?
• Is only the count needed, or the path too?

What a strong answer covers

• BFS over squares from the start with a visited set, stopping at the target.
• Symmetry: fold the target into the first quadrant (abs), and bound the search to a small margin around the rectangle [0, x] × [0, y] (allowing a step or two below zero, which (1, 0) and (1, 1) need).
• Bidirectional BFS to cut the explored area.
• Complexity proportional to the area searched, about O(x · y).
• The closed-form or DP-on-distance alternatives, mentioned as optional.

Follow-ups

• A finite n x n board with blocked squares.
• Return one shortest path.
• Many queries: precompute distances once within the bound.