We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Knight Moves

Number: 1142

Difficulty: Medium

Paid? Yes

Companies: Meta, Amazon, LinkedIn, Citadel, Microsoft, IMC, Google

Problem Description

Given an infinite chess board, a knight starting at [0, 0] can make 8 possible moves. The goal is to determine the minimum number of moves needed for the knight to reach a target square [x, y]. The board spans from –infinity to +infinity, and it is guaranteed that a solution exists.

Key Insights

  • Leverage the symmetry of the chessboard by converting target coordinates to their absolute values.
  • Use a Breadth-First Search (BFS) because all moves have equal weight, ensuring the first encounter with the target is the minimal path.
  • Prune the search space by only considering positions that are likely beneficial (e.g., positions having coordinates not far less than –1).
  • Track visited states to avoid redundant processing.
  • Optimize by bounding the search region relative to the target distance.

Space and Time Complexity

Time Complexity: O(n) where n is the number of positions processed during the BFS
Space Complexity: O(n) due to the storage requirements for the BFS queue and the visited set

Solution

We solve the problem using a BFS starting from the origin. First, normalize the target by taking the absolute value of x and y. BFS is then applied by exploring all eight possible knight moves at each step. Each move generates a new position that is enqueued if it hasn't been visited and falls within a reasonable bound (e.g., coordinates >= -1). The search terminates as soon as the target position is reached.

Code Solutions

# Python solution using BFS:
from collections import deque

def minKnightMoves(x, y):
    # Normalize target coordinates using symmetry
    x, y = abs(x), abs(y)
    
    # Possible knight moves (dx, dy)
    moves = [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]
    
    # BFS queue stores tuples of the form (current_x, current_y, move_count)
    queue = deque([(0, 0, 0)])
    
    # Set to track visited positions to prevent cycles
    visited = {(0, 0)}
    
    # Process BFS
    while queue:
        curr_x, curr_y, move_count = queue.popleft()
        
        # Return the current move count if target is reached
        if curr_x == x and curr_y == y:
            return move_count
        
        # Explore all knight moves
        for dx, dy in moves:
            next_x, next_y = curr_x + dx, curr_y + dy
            
            # Prune search space: only process positions with valid bounds
            if (next_x, next_y) not in visited and next_x >= -1 and next_y >= -1:
                visited.add((next_x, next_y))
                queue.append((next_x, next_y, move_count + 1))
    
    return -1  # Unreachable because a solution always exists

# Example test
#print(minKnightMoves(5, 5))
← Back to All Questions