LeetCode 1197 - Minimum Knight Moves

This problem asks us to compute the minimum number of moves a knight needs to travel from the origin [0, 0] to a target position [x, y] on an infinite chessboard.

leetcodemediumbreadth-first-search

LeetCode Problem 1197

Difficulty: 🟡 Medium
Topics: Breadth-First Search

Solution

Problem Understanding

This problem asks us to compute the minimum number of moves a knight needs to travel from the origin [0, 0] to a target position [x, y] on an infinite chessboard. The knight moves in an "L-shape," which means it can move two squares in one cardinal direction (up, down, left, right) and one square in the perpendicular direction. Each move is counted as a single step.

The inputs x and y represent the target coordinates. They can be negative, indicating that the target is in one of the quadrants left or below the origin. The output is a single integer representing the minimum number of knight moves required to reach [x, y].

Constraints are -300 <= x, y <= 300 and 0 <= |x| + |y| <= 300. This tells us that the target is relatively close to the origin despite the board being infinite. It also allows us to use breadth-first search without worrying about unbounded memory, as the search space is practically constrained. Important edge cases include coordinates that are very close to the origin, negative coordinates, and positions along axes, as a naive BFS could accidentally explore unnecessary quadrants. The problem guarantees that a solution exists, so we do not need to handle unreachable positions.

Approaches

A brute-force approach is to perform a BFS from [0, 0], exploring all 8 possible knight moves at each step, until reaching the target [x, y]. This approach is correct because BFS guarantees that the first time a node is reached, it is via the shortest path. However, BFS on the full infinite board could explore redundant positions in all four quadrants, making it slow.

The key insight for optimization is symmetry: because the knight's moves are symmetric, the shortest path to [x, y] is identical to the shortest path to [|x|, |y|]. Thus, we only need to search in the first quadrant (x >= 0, y >= 0). Additionally, instead of exploring the full infinite board, we can bound our BFS to a region around the target, as it is guaranteed that the knight will not need to move too far outside the bounding box of [0, 0] to [|x|, |y|].

Approach Time Complexity Space Complexity Notes
Brute Force BFS O(8^( x +
Optimized BFS with Symmetry O( x *

Algorithm Walkthrough

  1. Convert the target coordinates to the first quadrant using absolute values: x = abs(x) and y = abs(y). This reduces the search space due to symmetry of knight moves.
  2. Initialize a queue for BFS starting at (0, 0) with step count 0. Also, maintain a visited set to prevent revisiting positions.
  3. Define the 8 possible knight moves as pairs of offsets: (2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1).
  4. While the queue is not empty, pop the front node (cx, cy, steps). If (cx, cy) equals (x, y), return steps.
  5. For each of the 8 moves, compute the new coordinates (nx, ny) = (cx + dx, cy + dy).
  6. If (nx, ny) is non-negative and not visited, add (nx, ny, steps + 1) to the queue and mark it visited.
  7. Repeat until the target is reached.

Why it works: BFS guarantees that the first time a node is reached, it is via the minimum number of steps because each move is considered at the same "level." Using symmetry ensures we do not explore unnecessary negative coordinates. The visited set prevents cycles and repeated work.

Python Solution

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x, y = abs(x), abs(y)
        directions = [(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)]
        queue = deque([(0, 0, 0)])
        visited = set([(0, 0)])
        
        while queue:
            cx, cy, steps = queue.popleft()
            if (cx, cy) == (x, y):
                return steps
            for dx, dy in directions:
                nx, ny = cx + dx, cy + dy
                if nx >= -1 and ny >= -1 and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    queue.append((nx, ny, steps + 1))

This Python solution first maps the target to the first quadrant and then performs BFS. We initialize the queue with (0,0,0) to track coordinates and step count. The visited set ensures each position is visited at most once. The check nx >= -1 and ny >= -1 is a subtle optimization to avoid exploring positions far outside the origin that are never needed to reach the first quadrant target. Each iteration explores all 8 knight moves systematically.

Go Solution

package main

import "container/list"

func minKnightMoves(x int, y int) int {
    x, y = abs(x), abs(y)
    directions := [8][2]int{{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}}
    visited := make(map[[2]int]bool)
    queue := list.New()
    queue.PushBack([3]int{0,0,0})
    visited[[2]int{0,0}] = true

    for queue.Len() > 0 {
        elem := queue.Front()
        queue.Remove(elem)
        node := elem.Value.([3]int)
        cx, cy, steps := node[0], node[1], node[2]
        if cx == x && cy == y {
            return steps
        }
        for _, d := range directions {
            nx, ny := cx+d[0], cy+d[1]
            key := [2]int{nx, ny}
            if nx >= -1 && ny >= -1 && !visited[key] {
                visited[key] = true
                queue.PushBack([3]int{nx, ny, steps+1})
            }
        }
    }
    return 0
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

The Go implementation mirrors the Python BFS approach. We use a list.List for the queue and a map for visited positions. Arrays are used to store coordinates and steps. The main differences include explicit use of the abs function and handling slices vs tuples.

Worked Examples

Example 1: x = 2, y = 1

Queue Current Node Steps Next Nodes
[(0,0,0)] (0,0,0) 0 (2,1,1),(1,2,1),...
[(2,1,1),...] (2,1,1) 1 Target reached, return 1

Example 2: x = 5, y = 5

Queue Current Node Steps Next Nodes
[(0,0,0)] (0,0,0) 0 (2,1,1),(1,2,1),...
[(2,1,1),(1,2,1),...] (2,1,1) 1 (4,2,2),(3,3,2),...
... ... ... ...
... (5,5,4) 4 Target reached, return 4

Complexity Analysis

Measure Complexity Explanation
Time O( x
Space O( x

The time complexity is reduced compared to brute-force because we exploit symmetry and prune exploration to the first quadrant. Space complexity follows the number of unique positions visited.

Test Cases

# provided examples
assert Solution().minKnightMoves(2, 1) == 1  # simple move along x-axis
assert Solution().minKnightMoves(5, 5) == 4  # general case

# boundary values
assert Solution().minKnightMoves(0, 0) == 0  # origin, no moves needed
assert Solution().minKnightMoves(1, 0) == 3  # requires 3 moves
assert Solution().minKnightMoves(0, 1) == 3  # symmetric to above