Leetcode 1197. Minimum Knight Moves

Problem Explanation

The knight starts its movement from the (0,0) position on an infinite sized chess board with every square having a Cartesian coordinate. The problem is to determine minimum steps required by the knight to reach a specific given position (x,y).

Given, each move for the knight is two squares in the cardinal direction i.e. north, south, east or the west and then one square in an orthogonal direction i.e. a direction which is not parallel to the borders of chess board.

Therefore, the steps move the knight are defined as (2,1) or (1,2).The knight can land on any position on the chess board but the goal is to minimize the number of steps required to reach the final position (x,y).

Both x and y are the coordinates of the final square where the knight has to reach and it's guaranteed that a solution will exist. The input x and y are given where |x| + |y| <= 300.

For instance, If x is 2 and y is 1, then the knight can directly reach the square in a single step as [0,0] → [2, 1]. Similarly, for x and y as 5, the knight requires a minimum of 4 moves as [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5].

Approach

The memoization technique has been used to make it easier to solve this problem. In this technique, if a a previously calculated result is there in the cash (hashmap or dictionary), it's used directly. If not, the calculation is done and the result is stored in the cashier for future.

The use of 'memo' hashmap stores the minimum moves the knight makes from (0,0) to (x,y). We make use of recursion strucure with memo[] where the knight starts from (0,0) position and moves one step at a time to (x,y), tracking the minimum number of steps. The recursive call dp(x-2, y-1) computes moving two steps on x and one on y and dp(x-1, y-2) computes one step on x and two on y.

So, once either ways of the move is made, one step of the knight is considered. After either type of moves, the control goes back to dp(), checking the moves in hashmap. If the knight's position is not in the hashmap, track the number of knight’s steps and store it in hashmap.

Python

1
2python
3class Solution():
4    def steps(self, x, y):
5        memo = {(0, 0): 0, (1, 1): 2, (2, 0): 2, (2, 2): 4}    # Memoization initialization as it starts from (0,0)
6        return self.dp(x,y,memo)
7    
8    def dp(self, x, y, memo):       
9        x, y = abs(x), abs(y)
10        if x < y: x, y = y, x       # Basically save knight's steps from (0,0) to (x, y)
11        if (x,y) not in memo:
12            if (x, y - 2) not in memo:
13                memo[x, y] = min(self.dp(x - 2, y - 1, memo), self.dp(x - 1, y - 2, memo)) + 1
14        return memo[x, y]
15
16s = Solution()
17print(s.steps(5,5))

In the python solution, initially a recursive function is defined to compute either of the move, two steps on x and one on y or one step on x and two on y using dp(x-2, y-1, memo) or dp(x-1, y-2, memo). Also, the number of steps the knight makes is also tracked and returned at the end as the solution.

Java

1
2java

Let's skip Java for now.

JavaScript

1
2javascript
3TODO

Let's skip JavaScript for now.

C++

1
2C++
3class Solution {
4public:
5    int minKnightMoves(int x, int y) {
6        static int dx[] = {-1, -1, -2, -2, 1, 1, 2, 2};
7        static int dy[] = {-2, 2, -1, 1, -2, 2, -1, 1};
8        unordered_map<int, unordered_map<int, int>> visited;
9        x = abs(x);
10        y = abs(y);
11        visited[0][0] = 1;
12        queue<pair<int, int>> q;
13        q.push({0, 0});
14        while (true) {
15            auto cell = q.front();
16            q.pop();
17            if (!visited[cell.first + x][cell.second + y]) {
18                visited[cell.first + x][cell.second + y] = visited[cell.first][cell.second] + 1;
19                for (int i = 0; i < 8; ++i) {
20                    q.push({dx[i] + cell.first + x, dy[i] + cell.second + y});
21                }
22            } else if (visited[cell.first + x][cell.second + y] == 2) {
23                return visited[cell.first][cell.second];
24                break;
25            }
26        }
27        return -1;
28    }
29};

In this solution, Breadth-First Search (BFS) algorithm has been implemented. Queue data structure is also used in this algorithm to keep a track of all the next positions to be visted.

C#

1
2C#
3public class Solution {
4    private int[][] dirs = new int[8][]{
5        new int[2] {-2, -1}, 
6        new int[2] {-2, 1}, 
7        new int[2] {-1, -2}, 
8        new int[2] {-1, 2}, 
9        new int[2] {1, -2}, 
10        new int[2] {1, 2}, 
11        new int[2] {2, -1}, 
12        new int[2] {2, 1}
13    };
14    
15    public int MinKnightMoves(int x, int y) {
16        if(x==0 && y==0) return 0;
17        x = Math.Abs(x);
18        y = Math.Abs(y);
19        Queue<int[]> queue = new Queue<int[]>();
20        queue.Enqueue(new int[2] {0, 0});
21        int count = 0;
22        bool[][] visited = new bool[605][];
23        for(int i=0; i<605; i++)
24        {
25            visited[i] = new bool[605];
26        }
27        
28        while(queue.Count > 0)
29        {
30            int levelSize = queue.Count;
31            for(int i=0; i<levelSize; i++)
32            {
33                int[] current = queue.Dequeue();
34                if(current[0] == x && current[1] == y) return count;
35                foreach(var dir in dirs)
36                {
37                    int newx = dir[0] + current[0], newy = dir[1] + current[1];
38                    if(newx >= -2 && newx <= x + 2 && newy >= -2 && newy <= y + 2 && !visited[newx + 302][newy + 302]){
39                        queue.Enqueue(new int[2] {newx, newy});
40                        visited[newx+302][newy+302] = true;
41                    }
42                }
43            }
44            count++;
45        }
46        throw new InvalidOperationException();
47    }
48}

This solution uses the BFS algorithm and a queue data structure same as the C++ solution. A 2D boolean array 'visited' of size 605x605 is created. This array stores the positions of the knight already visited during the traversal. All the 8 possible moves of the knight are stored in an integer array 'dirs'.## Java

1
2java
3import java.util.LinkedList;
4import java.util.Queue;
5
6class Solution {
7    public int minKnightMoves(int x, int y) {
8        int[][] moves = new int[][] {{2, 1},{1, 2},{-1, 2},{-2, 1},{-2, -1},{-1, -2},{1, -2},{2, -1}};
9        boolean[][] visited = new boolean[605][605];
10
11        Queue<int[]> queue = new LinkedList<>();
12        queue.add(new int[] {0, 0, 0});
13        while (!queue.isEmpty()) {
14            int[] info = queue.poll();
15            if (info[0] == x && info[1] == y)
16                return info[2];
17            for (int[] move : moves) {
18                int nx = info[0] + move[0];
19                int ny = info[1] + move[1];
20                if (nx >= -2 && nx <= x+2 && ny >= -2 && ny <= y+2 && !visited[nx+302][ny+302]) {
21                    queue.add(new int[] {nx, ny, info[2] + 1});
22                    visited[nx+302][ny+302] = true;
23                }
24            }
25        }
26        return -1;
27    }
28}

The above java solution uses Breadth-First Search(BFS) and simulates the moves of the knight by adding all possible combinations of a knight's steps to the queue. For each step, we update the current steps and check if the knight has reached the target. If the destination is reached, we return the number of steps. If not, continue to simulate the next step. The BFS ensures that we find the minimum steps to the destination. The boolean "visited" matrix is used to avoid revisits.

JavaScript

1
2javascript
3function minKnightMoves(x, y) {
4    const steps = [[-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1]];
5    const visited = new Array(605).fill().map(() => new Array(605).fill(false));
6    const queue = [[0, 0, 0]];
7
8    x = Math.abs(x), y = Math.abs(y);
9    while (queue.length > 0) {
10        const [x1, y1, s] = queue.shift()
11        if (x1 === x && y1 === y) return s;
12
13        for (let [dx, dy] of steps) {
14            const nx = x1 + dx, ny = y1 + dy;
15            if (nx >= -2 && nx <= x + 2 && ny >= -2 && ny <= y + 2 && !visited[nx + 302][ny + 302]) {
16                visited[nx + 302][ny + 302] = true;
17                queue.push([nx, ny, s + 1]);
18            }
19        }
20    }
21  
22    return -1;
23}
24
25console.log(minKnightMoves(5,5))

The JavaScript solution is similar to the Python and Java solutions where Breadth-First Search(BFS) is implemented using a queue. The 'visited' is a 2D boolean array created to keep track of the already visited positions by the knight. For each movement by the knight, the possibility of a valid move is checked first if it lies within the chess board limits, then the next position of knight after making this move is added to the queue. We continue the process till the knight reaches the desired position (x, y) and return the number of steps to reach there as the result.