Minimum Knight Moves LeetCode Solution

Problem Statement

Minimum Knight Moves LeetCode Solution – In an infinite chessboard 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 needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example

Test Case 1:

Input:

x = 2

y = 1

Output:

1

Explanation

[0, 0] -> [2, 1]

Approach:

As hint suggests we can simulate all steps because the limits for the possible x and y are low (+-300). Also, a good catch is to work with abs(x) and abs(y) – it makes code simpler and doesn’t affect the answer – just imagine that it’s a mirrored image in the case of negative x and y.

We do the BFS style – from every cell we make all possible moves checking if we reach the target and if the cell has been visited before. If not – mark the cell as visited, store it in the BFS queue and continue the same loop.

Because it’s BFS we’ll get the minimum number of moves. If we met this cell before that it’s picked up by some other previous path and we can discard this current path.

We store possible moves in a 2D array, 8 elements that store increments of x and y coordinates. To store the next cell for the BFS and visited cells we can use encoding – just multiply x by something > 600 (from -300 to 300) and add y. Multiplication can be replaced by bit shift – it’s faster. 10 bits are enough – it gives 1024.

The problem statement asks us to find the minimum number of moves to reach a target position {x,y} on an infinite chessboard from {0,0}. The key point to observe here is that we can reduce this to a graph. 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 another. This leads to an undirected uniform weighted graph. Thus the shortest distance to the target position is our answer. Since the graph is undirected and has uniform weights we can use bfs to calculate the answer.

Algorithm:

• 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.

Code for Minimum Knight Moves

Java Program

class Solution {
    static class Pair{
        int x;
        int y;
        
        public Pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    
    public int minKnightMoves(int x, int y) {
        
        int[] dx={-1,1,2,2,1,-1,-2,-2};
        int[] dy={2,2,1,-1,-2,-2,-1,1};
        
        boolean[][] visited=new boolean[601][601];
        x+=300;
        y+=300;
        
        Queue<Pair> q=new LinkedList<>();
        q.add(new Pair(300,300));
        
        int g=1;
        int l=0;
        
        while(!q.isEmpty()){
            if(g==0){
                g=q.size();
                l++;
            }

            Pair p=q.remove();
            visited[p.x][p.y]=true;
            g--;
            
            if(p.x==x && p.y==y)
                return l;
            
            for(int i=0;i<8;i++){
                if(p.x+dx[i]>=0 && p.y+dy[i]>=0 && p.x+dx[i]<=600 && p.y+dy[i]<=600 && !visited[p.x+dx[i]][p.y+dy[i]]){
                    visited[p.x+dx[i]][p.y+dy[i]]=true;
                    q.add(new Pair(p.x+dx[i],p.y+dy[i]));
                }
            }
        }
        return -1;
    }
}

C++ Program

class Solution {
public:
    int minKnightMoves(int x, int y) {
        x=abs(x);
        y=abs(y);
     vector<pair<int, int>> direction {{2,1}, {-2,1},{2,-1},{-2,-1}, 
                                   {1,2},{1,-2}, {-1,2},{-1,-2}};   
        pair<int, int> start {0,0};
        int hops = 0;
       
        queue<pair<int, int> > q;
        q.push(start);
        
        set<pair<int, int>> visited;
        while(!q.empty()){
            
            int q_size = q.size();
            
            for(int i=0;i<q_size;i++)
            {
                
                pair<int, int> p = q.front();
                visited.insert(p);
                if(p.first==x&&p.second==y) return hops;
                q.pop();
                for(auto d: direction)
                {
                        if(visited.find({p.first+d.first,p.second+d.second})==visited.end() && p.first+d.first>= -2 && p.second+d.second>= -2)
                    {
                        q.push({p.first+d.first, p.second+d.second});
                        visited.insert ({p.first+d.first, p.second+d.second});
                    }
                }
                    
            }
             hops++;
            
        }
         
        return -1;
    }
};

Complexity Analysis for Minimum Knight Moves LeetCode Solution

Time Complexity
O(n)

Space Complexity
O(2n) -> O(n)