Interview Coaching
Mock Interviews
Learn
System Design
DSA
Behavioral
Interview Insights
Minimum Knight Moves
DESCRIPTION (credit Leetcode.com)
You are given a chessboard of infinite size where the coordinates of each cell are defined by integer pairs (x, y). The knight piece moves in an L-shape, either two squares horizontally and one square vertically, or two squares vertically and one square horizontally.
Write a function to determine the minimum number of moves required for the knight to move from the starting position (0, 0) to the target position (x, y). Assume that it is always possible to reach the target position, and that x and y are both integers in the range [-200, 200]
EXAMPLES
Example 1:
Input:
x = 1 y = 2
Output: 1
Explanation: The knight can move from (0, 0) to (1, 2) in one move.
Example 2:
x = 4 y = 4
Output: 4
Explanation: The knight can move from (0, 0) to (4, 4) in four moves ( [0, 0] -> [2, 1] -> [4, 2] -> [6, 3] -> [4, 4] )
Run your code to see results here
Explanation
Step 1: Initialize the Queue and Visited Set
Step 2: Perform BFS Traversal
Solution
from collections import dequeclass Solution:def minimum_knight_moves(self, x: int, y: int) -> int:directions = [(2, 1), (2, -1), (-2, 1), (-2, -1),(1, 2), (1, -2), (-1, 2), (-1, -2)]# Step 1: Initialize the queue and visited setqueue = deque([(0, 0, 0)])visited = set((0, 0))# Step 2: Perform BFS traversalwhile queue:# (cx, cy) is the current knight positioncx, cy, moves = queue.popleft()if (cx, cy) == (x, y):return moves# check all possible moves of the knight from the current positionfor dx, dy in directions:nx, ny = cx + dx, cy + dy# if the new position is not visited yet, add it to the queue# also mark it as visited and increment the number of movesif (nx, ny) not in visited:visited.add((nx, ny))queue.append((nx, ny, moves + 1))# if the target position is not reachable, return -1return -1
Loading comments...