Jobs

Interviews

Discussions

Minimum Knight Moves

Medium

Verily

2 views

Topics:

Graphs

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] -> [2, 1]

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] -> [2, 1] -> [4, 2] -> [3, 4] -> [5, 5]

Constraints:

-300 <= x, y <= 300
The answer is guaranteed to exist.

Minimum Knight Moves

Medium

Verily

2 views

Topics:

Graphs

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] -> [2, 1]

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] -> [2, 1] -> [4, 2] -> [3, 4] -> [5, 5]

Constraints:

-300 <= x, y <= 300
The answer is guaranteed to exist.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the x and y coordinates of the target position? Should I expect negative coordinates?
If the target position is the origin (0, 0), should I return 0?
Is it guaranteed that a path from (0, 0) to (x, y) always exists, or is it possible to have a target that is unreachable by the knight?
Are x and y integers?
Are there any memory constraints I should consider, given that the chessboard is infinite?

Brute Force Solution

Approach

Imagine a knight on a chessboard trying to reach a destination. The brute force approach is like trying every possible sequence of knight moves until we find one that gets us there. We keep track of the number of moves it takes for each sequence and pick the shortest one.

Here's how the algorithm would work step-by-step:

Start at the knight's initial position.
List all possible moves the knight can make from that spot.
For each of those possible moves, imagine the knight takes it and write down the new spot.
Now, for each of those new spots, again list all the moves the knight could make next.
Keep doing this, branching out like a tree of possible moves, until you reach the destination.
As you explore each path, keep track of how many moves it took to get there.
Once you reach the destination, compare the number of moves from all the different paths that got you there, and pick the path with the fewest moves.

Code Implementation

def minimum_knight_moves_brute_force(target_row, target_column):
    possible_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
    queue = [((0, 0), 0)]
    visited = set()
    visited.add((0, 0))

    while queue:
        (current_row, current_column), moves = queue.pop(0)

        if current_row == target_row and current_column == target_column:
            return moves

        for row_change, column_change in possible_moves:
            new_row = current_row + row_change
            new_column = current_column + column_change

            # Avoid cycles and redundant paths
            if (new_row, new_column) not in visited:

                visited.add((new_row, new_column))
                queue.append(((new_row, new_column), moves + 1))

    return -1 # Should not reach here, but good to have a return

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(8^d) – The algorithm explores possible knight moves in a breadth-first manner, expanding outwards from the starting position. At each position, the knight has up to 8 possible moves. The search continues until a path of length 'd' (the optimal number of moves) is found to the destination. Therefore, in the worst case, the algorithm explores roughly 8^d possible paths. Thus, the time complexity is exponential in the number of moves, 'd', to reach the target.

Space Complexity

O(N^2) – The algorithm explores possible knight moves breadth-first, effectively building a tree of moves. To avoid revisiting locations, it likely keeps track of visited positions, which in the worst case, could cover the entire chessboard up to a certain distance from the starting position. Assuming the target is reachable within an N x N area around the origin (where N represents the maximum coordinate value of the target), the space complexity is dominated by the visited set, which could store up to O(N^2) positions. Therefore, the auxiliary space is O(N^2).

Optimal Solution

Approach

The best way to find the fewest knight moves is to explore possibilities in order of their distance from the start, like ripples in a pond. We use a method that guarantees we find the shortest path first, stopping when we reach the target.

Here's how the algorithm would work step-by-step:

Imagine the chessboard as a graph, where each square is a point and each knight move is a connection between points.
Start at the knight's initial position and consider it move zero.
Look at all the squares the knight can reach in one move from the starting point. Assign each of those squares a move number of one.
Next, look at all the squares the knight can reach in one more move from those squares we just marked as one move away. Assign each of *those* squares a move number of two, unless they already have a move number. The key is to NOT revisit or reassign a square if you've already reached it.
Keep doing this, increasing the move number each time, until you reach the target square.
The move number you assigned to the target square is the minimum number of moves required.

Code Implementation

from collections import deque

def minimum_knight_moves(target_x, target_y):
    queue = deque([(0, 0, 0)])
    visited = set()
    visited.add((0, 0))
    
    # Possible knight moves.
    knight_moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
                    (2, 1), (2, -1), (-2, 1), (-2, -1)]

    while queue:
        current_x, current_y, moves = queue.popleft()

        if current_x == target_x and current_y == target_y:
            return moves

        for move_x, move_y in knight_moves:
            next_x = current_x + move_x
            next_y = current_y + move_y
            
            # Only process unvisited squares
            if (next_x, next_y) not in visited:
                # We add to visited before the queue.
                visited.add((next_x, next_y))
                queue.append((next_x, next_y, moves + 1))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The chessboard can be visualized as a graph where each cell is a node. In the worst-case scenario, the algorithm might need to explore all reachable cells on the board to find the target. Let 'n' represent the maximum dimension of the board, effectively representing the distance the knight needs to travel in both x and y coordinates from the origin (0,0) to the target, as the origin is the knight's starting location. The algorithm expands outwards in all possible knight moves from each visited cell. This breadth-first search explores up to n*n cells on the board. For each cell explored, we examine a constant number (at most 8) of potential knight moves. Thus, the time complexity is proportional to the number of cells explored, leading to a total of O(n²) operations in the worst case.

Space Complexity

O(N^2) – The algorithm explores the chessboard using a breadth-first search, potentially visiting every square. It implicitly maintains a queue (though not explicitly mentioned, exploring possibilities in order implies a queue) to track squares to explore and a visited set (implied by the phrase 'NOT revisit or reassign a square') to prevent revisiting. In the worst case, the queue and visited set could store information about all N^2 squares of the chessboard, where N is the dimension of the board. Therefore, the auxiliary space is proportional to N^2.

Edge Cases

Case	How to Handle
Target is at the origin (0, 0)	Return 0 immediately as no moves are needed.
Target coordinates are far from the origin (large x, y)	BFS scales relatively well but might require significant memory; consider iterative deepening A* search or heuristic optimization for extremely large coordinates.
Target coordinates are negative (x < 0 or y < 0)	Leverage the symmetry of the knight's movement to transform negative coordinates to positive ones by taking absolute values or reflecting across axes to reduce redundant calculations.
Coordinates are close to origin like (1,1) or (2,0)	BFS will find the optimal solution quickly since it explores neighbors level by level.
Integer overflow for extremely large coordinates (x,y) during distance calculation if not handled properly	Use appropriate data types (e.g., long or long long in C++, Python integers) to prevent potential integer overflows during BFS calculations or when determining visited nodes bounds.
The knight can return to a visited position, creating cycles	Maintain a 'visited' set or map to avoid re-exploring already visited positions, preventing infinite loops and ensuring optimal path finding.
Memory exhaustion due to extremely large exploration space	Implement iterative deepening BFS (IDBFS) or A* search with a suitable heuristic (e.g. Manhattan distance) to prioritize promising paths and limit memory usage.
Target x or y coordinate are non-integer numbers	Cast the input to integer, or report invalid input.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the x and y coordinates of the target position? Should I expect negative coordinates?
If the target position is the origin (0, 0), should I return 0?
Is it guaranteed that a path from (0, 0) to (x, y) always exists, or is it possible to have a target that is unreachable by the knight?
Are x and y integers?
Are there any memory constraints I should consider, given that the chessboard is infinite?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the knight's initial position.
List all possible moves the knight can make from that spot.
For each of those possible moves, imagine the knight takes it and write down the new spot.
Now, for each of those new spots, again list all the moves the knight could make next.
Keep doing this, branching out like a tree of possible moves, until you reach the destination.
As you explore each path, keep track of how many moves it took to get there.
Once you reach the destination, compare the number of moves from all the different paths that got you there, and pick the path with the fewest moves.

Code Implementation

def minimum_knight_moves_brute_force(target_row, target_column):
    possible_moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]
    queue = [((0, 0), 0)]
    visited = set()
    visited.add((0, 0))

    while queue:
        (current_row, current_column), moves = queue.pop(0)

        if current_row == target_row and current_column == target_column:
            return moves

        for row_change, column_change in possible_moves:
            new_row = current_row + row_change
            new_column = current_column + column_change

            # Avoid cycles and redundant paths
            if (new_row, new_column) not in visited:

                visited.add((new_row, new_column))
                queue.append(((new_row, new_column), moves + 1))

    return -1 # Should not reach here, but good to have a return

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the chessboard as a graph, where each square is a point and each knight move is a connection between points.
Start at the knight's initial position and consider it move zero.
Look at all the squares the knight can reach in one move from the starting point. Assign each of those squares a move number of one.
Next, look at all the squares the knight can reach in one more move from those squares we just marked as one move away. Assign each of *those* squares a move number of two, unless they already have a move number. The key is to NOT revisit or reassign a square if you've already reached it.
Keep doing this, increasing the move number each time, until you reach the target square.
The move number you assigned to the target square is the minimum number of moves required.

Code Implementation

from collections import deque

def minimum_knight_moves(target_x, target_y):
    queue = deque([(0, 0, 0)])
    visited = set()
    visited.add((0, 0))
    
    # Possible knight moves.
    knight_moves = [(1, 2), (1, -2), (-1, 2), (-1, -2),
                    (2, 1), (2, -1), (-2, 1), (-2, -1)]

    while queue:
        current_x, current_y, moves = queue.popleft()

        if current_x == target_x and current_y == target_y:
            return moves

        for move_x, move_y in knight_moves:
            next_x = current_x + move_x
            next_y = current_y + move_y
            
            # Only process unvisited squares
            if (next_x, next_y) not in visited:
                # We add to visited before the queue.
                visited.add((next_x, next_y))
                queue.append((next_x, next_y, moves + 1))

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Target is at the origin (0, 0)	Return 0 immediately as no moves are needed.
Target coordinates are far from the origin (large x, y)	BFS scales relatively well but might require significant memory; consider iterative deepening A* search or heuristic optimization for extremely large coordinates.
Target coordinates are negative (x < 0 or y < 0)	Leverage the symmetry of the knight's movement to transform negative coordinates to positive ones by taking absolute values or reflecting across axes to reduce redundant calculations.
Coordinates are close to origin like (1,1) or (2,0)	BFS will find the optimal solution quickly since it explores neighbors level by level.
Integer overflow for extremely large coordinates (x,y) during distance calculation if not handled properly	Use appropriate data types (e.g., long or long long in C++, Python integers) to prevent potential integer overflows during BFS calculations or when determining visited nodes bounds.
The knight can return to a visited position, creating cycles	Maintain a 'visited' set or map to avoid re-exploring already visited positions, preventing infinite loops and ensuring optimal path finding.
Memory exhaustion due to extremely large exploration space	Implement iterative deepening BFS (IDBFS) or A* search with a suitable heuristic (e.g. Manhattan distance) to prioritize promising paths and limit memory usage.
Target x or y coordinate are non-integer numbers	Cast the input to integer, or report invalid input.