Katkat
Back

Find Shortest Knight Path

WaymoSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to model a constrained movement pattern on a 2D grid as an unweighted graph and efficiently find the shortest path using Breadth-First Search (BFS).

Problem Statement

Given an N x N chessboard and two coordinates (start_x, start_y) and (end_x, end_y), find the minimum number of moves a knight must take to reach the destination. If the destination is unreachable (though not possible on a standard board without obstacles), return -1.

A knight moves in an 'L' shape: 2 squares in one cardinal direction (horizontal or vertical) and then 1 square perpendicular to that.

Function Signature

def min_knight_moves(n: int, start: tuple, end: tuple) -> int:

Constraints

  • 5 <= n <= 500
  • Coordinates are 0-indexed: 0 <= x, y < n
  • Time limit: 1 second

Example 1

Input: n = 8, start = (0, 0), end = (1, 2) Output: 1 Explanation: The knight reaches (1, 2) in exactly one move from (0, 0).

Example 2

Input: n = 8, start = (0, 0), end = (1, 1) Output: 2 Explanation: One possible path is (0,0) -> (2,1) -> (1,1).

Edge Cases

  • Starting position is the same as the ending position.
  • Coordinates are near the boundaries of the grid.

Hints

Hint 1

Model the chessboard as a graph where each square is a node and each valid knight move is an edge.

Hint 2

Since all moves have a weight of 1, BFS is the optimal algorithm for finding the shortest path.

Hint 3

Use a queue to track the current position and a distance map (or a visited set) to avoid redundant calculations and infinite loops.

Follow-up questions

  • How would your solution change if there were 'traps' (blocked squares) on the board that the knight cannot land on?
  • If the board were infinite, could you optimize the BFS? (e.g., exploiting board symmetry).
  • How would you calculate the path itself, not just the number of moves, and what is the space complexity of storing that path?