1197. Minimum Knight Moves

Problem Description

In this problem, we are given an infinite chess board that can be imagined as an endless grid with coordinates ranging from negative infinity to positive infinity. We have a chess piece—a knight—placed at the origin [0, 0] of this grid. The objective is to calculate the minimum number of moves that the knight must make to reach a specific square [x, y] on the chessboard.

A knight in chess moves in an L-shape: it can move two squares in one direction (either horizontally or vertically) and then make a 90-degree turn to move one square in a perpendicular direction. This gives the knight a total of eight possible moves at any given point.

The problem requires us to determine the least number of moves necessary to get the knight from its starting position [0, 0] to any target coordinates [x, y]. The question assures that it is always possible to reach the target square.

Intuition

The solution to this problem is guided by an approach known as Breadth-First Search (BFS), which is a common algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node in a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Here's how we apply BFS to solve this problem:

Start by enqueuing the initial position of the knight (0, 0).
Explore all possible moves a knight can make from its current position.
For each move, check if the new position matches the target position [x, y]. If so, we return the current number of moves taken to get there as our answer.
If the new position is not the target and has not been visited yet, add it to a queue for further exploration and mark it as visited.
Increase the move counter each time we've explored all positions at the current level of depth.
Repeat these steps until the target position is reached.

This process is efficient for finding the shortest path in an unweighted graph—or in this case, an infinite grid—where the distance between all adjacent nodes is equal.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First SearchBreadth-First SearchBinary SearchPriority Queue

I don’t know

Solution Approach

The solution uses Breadth-First Search (BFS), which is an algorithm well-suited for searching for the shortest path in an unweighted graph. In this case, the graph can be thought of as an infinite 2D grid where each cell is a node and each knight's move represents an edge connecting two nodes.

Breadth-First Search (BFS)

The BFS algorithm works level by level. Starting from a source node, BFS examines all neighbor nodes at the current depth before moving on to nodes at the next depth level. This method ensures that the path found to any node is the shortest one.

Data Structures Used

To implement BFS:

Queue q: A double-ended queue (deque in Python) is used to store nodes to explore in the order they were encountered.
Set vis: A set is used to keep track of visited nodes to prevent re-processing them.

Algorithm Steps

Initialization: Add the starting position, [0, 0], to the q queue and mark it as visited by adding it to the vis set. Initialize a step counter ans to zero.
Processing Nodes: Continue the process while there are nodes in the queue to explore.
- For each iteration (or level in the BFS), check all nodes currently in the queue.
- Remove a node from the front of the queue using popleft().
- If this node is the target [x, y], return the ans as the minimum number of steps.
Exploring Neighbors: For the current node at position (i, j), calculate all possible positions where the knight can move based on the defined moves in dirs.
- If a neighbor node (c, d) has not been visited, mark it as visited by adding it to the vis set and append it to the queue q.
Incrementing Steps: After exploring all nodes at the current depth, increment the ans counter by 1 before moving on to nodes at the next depth level.
Termination: If the target node [x, y] is reached, the current value of ans will be the minimum number of steps needed, and the function returns this value.

The loop continues until we reach the target node, at which point the function exits with the answer. The BFS guarantees that when we reach [x, y], it will be the shortest path due to the way BFS explores all paths of n length before moving to paths of n+1 length.

By using a set vis, the algorithm ensures each node is processed only once, avoiding redundant calculations and cycles which is crucial for efficiency on an infinite grid.

Overall, the BFS approach is efficient and guarantees that the shortest path will be found in a scenario like this where each move is considered of equal 'weight' or distance.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

O(1)O(n)O(n!)O(n^n)

I don’t know

Example Walkthrough

Let's go through a small example to illustrate how the solution approach works. Suppose we want to find the minimum moves for a knight to reach [2, 1] from [0, 0].

Initialization: We start by initializing our BFS. We enqueue the starting position [0, 0] into our queue q and add it to our visited set vis. The step counter ans is also initialized to 0.
Processing Nodes: At the first level of BFS (starting with ans = 0), the queue q contains just [0, 0].
Exploring Neighbors: From [0, 0], a knight can move to eight possible positions: [2, 1], [1, 2], [-1, 2], [-2, 1], [-2, -1], [-1, -2], [1, -2], and [2, -1]. We add each of these to the queue q (if not already visited) and add them to the visited set vis.
Incrementing Steps: There is no need to increment ans yet because we may find our target coordinates at this level. However, none of the positions we have right now from [0, 0] are the target.
Identifying the Target: The target [2, 1] is indeed one of the potential moves directly from [0, 0]. As soon as we discover this during our search of neighbors, we know that the minimum moves to reach [2, 1] from [0, 0] is one.
Termination: Since we have reached our target [2, 1], we can return ans which still holds the value 0. However, as we move directly from the starting point [0, 0] to the target [2, 1], we conclude that the number of moves required is 1.

This is a simple and ideal case where we found the target in the first set of moves from the starting position. In cases where the target position is not one of the initial possible moves, we continue the BFS iteration, each time exploring all possible moves from the positions currently in the queue, incrementing ans after all possible moves of the current ans have been explored, and repeating the process until the target [x, y] is found. The BFS ensures we find the shortest path due to its level-by-level exploration.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def minKnightMoves(self, x: int, y: int) -> int:
5        # Initialize a queue and start with the knight's initial position (0, 0).
6        queue = deque([(0, 0)])
7      
8        # The initial number of moves is set to zero.
9        moves_count = 0
10      
11        # Use a set to keep track of the visited positions to prevent revisits.
12        visited = {(0, 0)}
13      
14        # The possible moves a knight can take: 8 directions.
15        directions = ((-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1))
16      
17        # Run BFS until the queue is empty.
18        while queue:
19            # Process nodes level by level.
20            for _ in range(len(queue)):
21                current_i, current_j = queue.popleft()  # Current position
22              
23                # If the target position is reached, return the number of moves.
24                if (current_i, current_j) == (x, y):
25                    return moves_count
26              
27                # Explore all possible moves from the current position
28                for delta_i, delta_j in directions:
29                    new_i, new_j = current_i + delta_i, current_j + delta_j
30                  
31                    # If the new position is not yet visited, mark it as visited and add to queue.
32                    if (new_i, new_j) not in visited:
33                        visited.add((new_i, new_j))
34                        queue.append((new_i, new_j))
35          
36            # Increment the number of moves after expanding all nodes at the current level.
37            moves_count += 1
38      
39        # If we exit the while loop something went wrong, we should never reach here.
40        return -1
41

1import java.util.ArrayDeque;
2import java.util.Queue;
3
4class Solution {
5    public int minKnightMoves(int x, int y) {
6        // Offset coordinates by 310 to deal with negative indices since a knight can move backward.
7        x += 310;
8        y += 310;
9
10        // Starting moves count from (0, 0) which is at the center after offset
11        int moves = 0;
12
13        // Initialize queue for BFS and add starting position after offset
14        Queue<int[]> queue = new ArrayDeque<>();
15        queue.offer(new int[] {310, 310});
16
17        // Visited matrix to keep track of already visited points.
18        boolean[][] visited = new boolean[621][621];
19        visited[310][310] = true;
20
21        // Directions a knight can move: 8 possibilities
22        int[][] directions = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
23
24        while (!queue.isEmpty()) {
25            // Number of elements in the current level
26            for (int i = queue.size(); i > 0; --i) {
27                // Poll the first element in the queue
28                int[] point = queue.poll();
29
30                // Check if the current position is the target position
31                if (point[0] == x && point[1] == y) {
32                    return moves;
33                }
34
35                // Explore all possible moves from the current position
36                for (int[] direction : directions) {
37                    int nextX = point[0] + direction[0];
38                    int nextY = point[1] + direction[1];
39
40                    // Make sure the new position is within bounds and hasn't been visited
41                    if (nextX >= 0 && nextY >= 0 && nextX < visited.length && nextY < visited[nextX].length && !visited[nextX][nextY]) {
42                        visited[nextX][nextY] = true;
43                        queue.offer(new int[] {nextX, nextY});
44                    }
45                }
46            }
47            // Increment moves after finishing all moves of the current level
48            ++moves;
49        }
50        // Return -1 if we never reach the destination position (should not happen with correct logic)
51        return -1;
52    }
53}
54

1#include <vector>
2#include <queue>
3#include <utility>
4
5class Solution {
6public:
7    int minKnightMoves(int x, int y) {
8        // Offset the x and y to avoid negative index issues.
9        // The number 310 is chosen to handle negative coordinates 
10        // because a knight cannot be more than 310 moves away from the origin in any direction.
11        x += 310;
12        y += 310;
13
14        // Initialize the answer to 0, which represents the number of moves.
15        int minMoves = 0;
16        std::queue<std::pair<int, int>> queue; // Queue to manage BFS.
17        queue.push({310, 310}); // Starting point (0,0) with the offset.
18
19        // Visited matrix to keep track of visited cells.
20        std::vector<std::vector<bool>> visited(700, std::vector<bool>(700, false));
21        visited[310][310] = true; // Mark the starting point as visited.
22
23        // Directions a knight can move on a chessboard.
24        std::vector<std::vector<int>> directions = {
25            {-2, 1}, {-1, 2}, {1, 2}, {2, 1},
26            {2, -1}, {1, -2}, {-1, -2}, {-2, -1}
27        };
28
29        // BFS Algorithm.
30        while (!queue.empty()) {
31            // Traverse nodes level by level.
32            for (int size = queue.size(); size > 0; --size) {
33                auto current = queue.front();
34                queue.pop();
35
36                // Check if we have reached the target (x, y) cell.
37                if (current.first == x && current.second == y) return minMoves;
38              
39                // Explore all possible moves from the current position.
40                for (auto& direction : directions) {
41                    int nextRow = current.first + direction[0];
42                    int nextCol = current.second + direction[1];
43
44                    // If the cell is not visited, mark it visited and add to the queue.
45                    if (!visited[nextRow][nextCol]) {
46                        visited[nextRow][nextCol] = true;
47                        queue.push({nextRow, nextCol});
48                    }
49                }
50            }
51            // Increment the number of moves after exploring all positions in current level.
52            ++minMoves;
53        }
54      
55        // If the function hasn't returned yet, something went wrong.
56        // With the BFS approach, however, we should always be able to return before hitting this line.
57        return -1;
58    }
59};
60

1type Point = [number, number];
2
3// Offset to handle negative coordinates. A knight cannot be more than 310 moves away from the origin.
4const OFFSET = 310;
5const BOARD_SIZE = 700; // Define board as 700x700 to include the offset space.
6
7let visited: boolean[][] = Array.from({ length: BOARD_SIZE }, () => Array(BOARD_SIZE).fill(false));
8
9const directions: Point[] = [
10  [-2, 1], [-1, 2], [1, 2], [2, 1],
11  [2, -1], [1, -2], [-1, -2], [-2, -1],
12];
13
14function minKnightMoves(x: number, y: number): number {
15    // Normalize the target coordinates with the offset.
16    x += OFFSET;
17    y += OFFSET;
18
19    let minMoves: number = 0;
20    let queue: Point[] = [[OFFSET, OFFSET]]; // Initialize BFS queue with the starting point (0, 0) with the offset.
21    visited[OFFSET][OFFSET] = true; // Mark the starting point as visited.
22
23    while (queue.length > 0) {
24        // Number of nodes at the current BFS level.
25        let levelSize: number = queue.length;
26
27        // Traverse nodes level by level.
28        for (let i = 0; i < levelSize; i++) {
29            let current: Point = queue.shift()!; // Retrieve and remove the first element.
30
31            // Check if the current position is the target position.
32            if (current[0] === x && current[1] === y) {
33                return minMoves;
34            }
35
36            // Explore all possible moves from current position.
37            directions.forEach(direction => {
38                let nextRow: number = current[0] + direction[0];
39                let nextCol: number = current[1] + direction[1];
40
41                // Check if the cell is within the board limits and not visited.
42                if (nextRow >= 0 && nextRow < BOARD_SIZE && nextCol >= 0 && nextCol < BOARD_SIZE && !visited[nextRow][nextCol]) {
43                    visited[nextRow][nextCol] = true;
44                    queue.push([nextRow, nextCol]);
45                }
46            });
47        }
48        // Increment the number of moves after exploring the current level.
49        minMoves++;
50    }
51
52    // Return -1 if no solution found, though BFS should always find the solution.
53    return -1;
54}
55
56// Reset visited matrix for a fresh computation.
57function resetVisited(): void {
58    visited = visited.map(row => row.fill(false));
59}
60

Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimumsAdd a heap to store the minimumsAdd a variable to track the minimumAdd a queue to store the minumums

I don’t know

Time and Space Complexity

The given Python code implements a breadth-first search (BFS) algorithm to find the minimum number of moves a knight can take to reach a given position (x, y) on an infinite chessboard, starting from position (0, 0). The time complexity and space complexity of this BFS algorithm are as follows:

Time Complexity

To analyze the time complexity, let's consider the increments to coordinates as potential moves from one square to another. For each move, we have 8 possible directions in which the knight can move. The BFS algorithm ensures that every position is visited only once, thanks to the vis set which tracks the visited positions.

Since the board is infinite, the maximum distance from the origin in terms of the number of moves can be represented by max(abs(x), abs(y)). This is because, in the worst-case scenario, we can consider moving diagonally (in L-shaped movements) towards the target, which is roughly max(abs(x), abs(y)) moves away. However, the actual number of moves requires considering the peculiarities of knight's movements. The BFS will have a branching factor of at most 8 (the possible moves the knight can make), and the depth will be proportional to the distance from the origin to the target.

Thus, the time complexity can be approximated as O(8^(d)) where d is the depth of the BFS, or more accurately, O((max(abs(x), abs(y)))^2) because each layer of BFS (which corresponds to one knight's move) potentially adds up to 8 new positions in the queue.

Space Complexity

The space complexity is primarily dictated by the storage required for the vis set and the q queue. The vis set contains all the unique positions we have visited during the BFS.

The space taken by the vis set is proportional to the number of elements in it, which is the number of unique positions the algorithm will visit, roughly the same as the time complexity, leading to an O((max(abs(x), abs(y)))^2) space complexity.
The q queue stores the positions that need to be explored. In the worst case, the queue could store all of the positions that we visit. Hence, the space complexity contributed by the q is similar to the vis set, O((max(abs(x), abs(y)))^2).

Overall, the space complexity of the algorithm is O((max(abs(x), abs(y)))^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1197. Minimum Knight Moves

Problem Description

Intuition

Solution Approach

Breadth-First Search (BFS)

Data Structures Used

Algorithm Steps

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity