Minimum Knight Moves — Daily Challenge May
Today’s question is from Daily Leetcode Coding Challenge — May Edition. It is a medium-tagged question. Let us look into the problem statement.
1197. Minimum Knight Moves
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:
Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]Understand the problem:
A Knight’s movement can be summarised as below in terms of coordinate increments considering a current position as x, y:
1. (x-1, y+2) ==> (-1, +2)
2. (x+1, y+2) ==> (+1, +2)
3. (x+2, y+1) ==> (+2, +1)
4. (x+2, y-1) ==> (+2, -1)
5. (x+1, y-2) ==> (+1, -2)
6. (x-1, y-2) ==> (-1, -2)
7. (x-2, y-1) ==> (-2, -1)
8. (x-2, y+1) ==> (-2, +1)As we see at a given coordinate the Knight can move to 8 different positions. From there it can move the next seven(1 will be the start position or position from where it came) places. The minimum number of steps can be found using BFS traversal.
Also since the initial position is at (0, 0) we can restrict the moves in the positive region or first quadrant. We can do so if we take the absolute value of the target coordinate. We can do so since we only need to find the minimum number of steps. Also, we keep track of visiting positions.
Code Implementation:
def minKnightMoves(x, y):
x , y = abs(x), abs(y)
possible_moves = [
(1, 2), (2, 1), (-1, 2),
(-2, 1), (-1, -2), (-2, -1),
(1, -2), (2, -1)
]
que = collections.deque([[0, 0, 0]])
visited = set()
visited.add((0, 0))
while que:
qx, qy, d = que.popleft()
if x == qx and y == qy:
return d
for dx, dy in possible_moves:
nx, ny = qx + dx, qy + dy
if (nx, ny) not in visited and nx >=-2 and ny>=-2:
visited.add((nx, ny))
que.append([nx, ny, d + 1])Complexity Analysis:
- Time complexity: O(max(x²,y²)). This is due to the fact that every place the Knight covers a radius of 2x or 2y. The number of cells inside this circle is the max of x² or y².
- Constant space: O(max(x²,y²)) at any level we store all nodes that can be reached from the previous level.
Approach 2
From the directions, we can optimize and only move in the (-1, -2) or (-2, -1) direction. In other words, the destination is always in the first quadrant. The moment we reach (0, 2) or (2, 0) or (1, 1) the knight cannot move further to (0, 0) or might go into the negative axis. If we are in (0, 2) move the night to (2, 1) then from there it could move to (0, 0). This takes 2 moves. The same applies to (1, 1) and (2,0). Similarly for (0, 1), it will need 3 steps to come back to (0, 0)
def minKnightMoves(self, x: int, y: int) -> int:
known_point_moves = {(0, 0): 0, (1, 1): 2, (1, 0): 3, (0, 1): 3, (2, 0): 2, (0, 2): 2} def dfs(x, y):
if (x, y) in known_point_moves:
return cache[(x, y)]
res = min(dfs(abs(x-1), abs(y-2)), dfs(abs(x-2), abs(y-1))) + 1
known_point_moves[(x, y)] = res
return res
return dfs(abs(x), abs(y))
