Minimum Knight Moves

Problem Highlights

🔗 Leetcode Link: https://leetcode.com/problems/minimum-knight-moves
💡 Problem Difficulty: Medium
⏰ Time to complete: __ mins
🛠️ Topics: Graphs, Breadth-First Search
🗒️ Similar Questions: Shortest Path in Binary Matrix, Open the Lock

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

How many neighbors do we have at each point?
- At each point, we can have 8 neighbors, and a shortest path may need moves in both horizontal directions. For example, reaching (1, 1) takes (0, 0) -> (2, -1) -> (1, 1): one move to the right and one to the left. So we cannot keep only the 4 neighbors on one side of a point.
How can we make sure neighbors are not added multiple times?
- You can use a data structure like a hashMap to make sure neighbors are not added multiple times.
How can we reduce this graph to find the minimum number of moves?
- Each position on the board can be thought of as a node. Edges can be thought of as possible moves for a knight from one position to other. This leads to an undirected uniform weighted graph. Thus the shortest distance to the target position is our answer.

    HAPPY CASE
    Input: x = 2, y = 1
    Output: 1
    
    Input: x = 5, y = 5
    Output: 4

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For graph problems, some things we want to consider are:

BFS: Use BFS to find the shortest path with optimizations:
1. don’t go down visited paths by using a set to keep track of visited paths.
2. optionally pruning positions that wander far from the target x,y (a single move that heads away can still be on a shortest path, as the quadrant note below shows).
At each point, we’ve got 8 coordinates (8 neighbors) that we can move to in any given location. As with normal BFS, we build a queue, keep track of what we’ve visited, and explore our 8 neighbors. Observe that our movements are completely symmetric. Whether our destination was (x,y), (x,-y), (-x,y), or (-x,-y), our answer would be the exact same. So what we can do is map the target to (|x|, |y|) and restrict our search space to roughly one quadrant (namely the 1st quadrant where x,y are both positive). We cannot ignore every neighbor outside quadrant 1, though: reaching (1, 1) in its minimum of 2 moves requires (0, 0) -> (2, -1) -> (1, 1), which briefly leaves the quadrant. As the Common Mistakes section notes, it is safe to ignore only neighbors that fall more than 2 squares outside quadrant 1. The implementations below skip this pruning and run a plain BFS.
DFS: DFS would explore one movement chain to its full depth before backtracking, so it does not naturally find the minimum number of moves this problem asks for. BFS is preferred because it explores positions in order of distance from the origin.
Implicit graph: The board is infinite, so the graph cannot be built up front as an adjacency list or an adjacency matrix. Both implementations below generate a square’s 8 neighbors on the fly from the knight-move offsets and store only the squares they have already visited.
Topological Sort: Does not apply. A topological ordering exists only for a directed acyclic graph, but every knight move can be reversed by the opposite move, so the graph is undirected and full of cycles.
Union Find: Does not apply. Union Find can tell whether two squares are in the same connected component, but it cannot measure how many moves separate them, and the minimum move count is what this problem asks for.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Find the minimum steps required to travel from one point to another point on a grid.

Start from {0,0}. The distance to {0,0} here is 0. Add this position to queue.
Keep performing BFS from each point present in the queue. At each step poll a point and explore all 8 possible tiles where the knight can land and add those points to the queue if not visited.
Thus each point reaches one more hop to the neighbor. And eventually reaches the target node.

⚠️ Common Mistakes

Avoid visiting the same cell again. You can realize that the problem is symmetric, i.e. all 4 of (±x, ±y) will have the same solution, so restrict the solution space to the first quadrant. It’s possible to reach (x, y) by going 1 step out of Q1 then returning to Q1, so max you can go out of Q1 is 2 steps in either direction.

4: I-mplement

Implement the code to solve the algorithm.

class Solution {
    public int minKnightMoves(int x, int y) {
        // the offsets in the eight directions
        int[][] offsets = {{1, 2}, {2, 1}, {2, -1}, {1, -2},
                {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};
        boolean[][] visited = new boolean[607][607];

        Deque<int[]> queue = new LinkedList<>();
        queue.addLast(new int[]{0, 0});
        int steps = 0;

        while (queue.size() > 0) {
            int currLevelSize = queue.size();
            // iterate through the current level
            for (int i = 0; i < currLevelSize; i++) {
                int[] curr = queue.removeFirst();
                if (curr[0] == x && curr[1] == y) {
                    return steps;
                }

                for (int[] offset : offsets) {
                    int[] next = new int[]{curr[0] + offset[0], curr[1] + offset[1]};
                    // align the coordinate to the bitmap
                    if (!visited[next[0] + 302][next[1] + 302]) {
                        visited[next[0] + 302][next[1] + 302] = true;
                        queue.addLast(next);
                    }
                }
            }
            steps++;
        }
        // move on to the next level
        return steps;
    }
}

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        # the offsets in the eight directions
        offsets = [(1, 2), (2, 1), (2, -1), (1, -2),
                   (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

        def bfs(x, y):
            visited = set()
            queue = deque([(0, 0)])
            steps = 0

            while queue:
                curr_level_cnt = len(queue)
                # iterate through the current level
                for i in range(curr_level_cnt):
                    curr_x, curr_y = queue.popleft()
                    if (curr_x, curr_y) == (x, y):
                        return steps

                    for offset_x, offset_y in offsets:
                        next_x, next_y = curr_x + offset_x, curr_y + offset_y
                        if (next_x, next_y) not in visited:
                            visited.add((next_x, next_y))
                            queue.append((next_x, next_y))

                # move on to the next level
                steps += 1

        return bfs(x, y)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Trace through your code with an input to check for the expected output
Catch possible edge cases and off-by-one errors and verify the code works for the happy and edge cases you created in the “Understand” section

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Let d = max(|x|, |y|), where (x, y) is the target.

Time Complexity: O(d^2). The BFS stops at the level equal to the knight distance of the target, and that distance grows linearly with d. A knight move changes each coordinate by at most 2, so every square the search enqueues lies inside a box whose side length is O(d), which holds O(d^2) squares. The visited check keeps every square from being enqueued more than once, apart from the start square (0, 0), which neither version marks as visited before the loop and which can therefore be enqueued one more time. A product bound such as O(xy) does not describe this search: it is zero for a target on an axis, such as (5, 0), even though the BFS still explores every square within the target’s knight distance. (For the target (0, 0) the loop returns on its first dequeue.)
Space Complexity: O(d^2) for the visited set and the queue in the Python version, which hold the squares explored so far. The Java version allocates a fixed 607 x 607 visited array sized for the problem’s |x| + |y| <= 300 constraint, so that array has the same size for every valid input, and its queue holds O(d^2) entries.