Practice/Google/Leetcode 1197. Minimum Knight Moves

Leetcode 1197. Minimum Knight Moves

CodingMust

Problem

On an infinitely large chessboard, a knight starts at position (0, 0). Given target coordinates (x, y), determine the minimum number of moves the knight needs to reach the target square.

A knight moves in an "L" shape: it can move two squares in one direction (horizontal or vertical) and then one square perpendicular to that direction. This gives the knight up to 8 possible moves from any position:

• (+2, +1), (+2, -1), (-2, +1), (-2, -1)
• (+1, +2), (+1, -2), (-1, +2), (-1, -2)

Return the minimum number of knight moves required to reach position (x, y) from (0, 0).

Requirements

1. Calculate the shortest path from (0, 0) to (x, y) using valid knight moves
2. Handle both positive and negative coordinates
3. Return 0 if the target is the origin (0, 0)
4. The solution must work efficiently for coordinates with absolute values up to 300

Constraints

• -300 ≤ x, y ≤ 300
• The chessboard is infinite (no boundary restrictions)
• Expected time complexity: O(max(|x|, |y|)²) or better
• Expected space complexity: O(max(|x|, |y|)²) or better

Examples

Example 1:

Input: x = 2, y = 1 Output: 1 Explanation: The knight can reach (2, 1) in one move directly from (0, 0).

Example 2:

Input: x = 5, y = 5 Output: 4 Explanation: One optimal sequence: (0,0) → (2,1) → (4,2) → (3,4) → (5,5)

Example 3:

Input: x = 0, y = 0 Output: 0 Explanation: The knight is already at the target position.

Example 4:

Input: x = -1, y = -1 Output: 2 Explanation: Due to symmetry, negative coordinates work the same as positive ones.