Minimum Knight Moves

BFS

Problem

Thought Process

• We care about the levels in this problem

• Infinite chess board meaning no boundaries

• BFS to look at all the neighbors

Solution

from collections import deque

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        q = deque()
        visited = set((0,0))
        q.append([0,0])
        steps = 0
        direc = [[-2,-1], [-2,1],[2,-1],[2,1],[-1,-2], [1,-2], [-1,2], [1,2]]
        x = abs(x)
        y = abs(y)
        
        while q:
            levelSize = len(q)
            for _ in range(levelSize):
                coor = q.popleft()
                xCoor = coor[0]
                yCoor = coor[1]
                
                if xCoor == x and yCoor == y:
                    return steps
                
                else:
                    for i in direc:
                        newX = xCoor + i[0]
                        newY = yCoor + i[1]
                
                        if (newX, newY) not in visited and (newX>=-2 and newY >= -2):
                
                            q.append([newX,newY])
                            visited.add((newX, newY))
            steps+=1 
            

Time Complexity:

• Time: O(n) where n is the number of moves we have to make

• Space: O(n) where n is the number of moves we have to make