Coding - Minimum Knight Moves

Problem Statement

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0]. A knight can move in 8 possible ways: [+/-1, +/-2] and [+/-2, +/-1]. Return the minimum number of steps needed to move the knight to square [x, y]. It is guaranteed the answer exists.

Examples

Example 1: Input: x = 2, y = 1 Output: 1 Explanation: [0, 0] → [2, 1]

Example 2: Input: x = 4, y = 5 Output: 3

Constraints

• -100000 <= x, y <= 100000

Hints

1. Let d be the Euclidean distance between the starting point and the target, and let m be the Manhattan distance. We know that the knight still must take in steps of either 1 or 2 in the Euclidean distance.
2. Since the knight is always taking steps that move it closer to the target, we can always reach the target in a number of moves that is at least m.
3. We can show that the knight will always reach the target in at most d moves.
4. If the knight reaches a point where it can reach the target in one move, it will do so. Otherwise, it will move to a point that reduces the Euclidean distance by at least 1.
5. Since the Euclidean distance between the starting point and the target is d, the knight will reach the target in at most d moves.
6. We can check all possible moves that the knight can make from its current position, and choose the one that reduces the Euclidean distance by the greatest amount. This can be done with a breadth-first search.