MediumNo. 1197LeetCode Premium
Minimum Knight Moves — LeetCode 1197 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Breadth-First Search
- Reading time
- 3 min
- Source
- leetcode.com
The problem
In an infinite chess board 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.
Example
- Input
- x = 2, y = 1
- Output
- 1
- Explanation
- [0, 0] → [2, 1]
Python solution
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
q = deque([(0, 0)])
ans = 0
vis = {(0, 0)}
dirs = ((-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1))
while q:
for _ in range(len(q)):
i, j = q.popleft()
if (i, j) == (x, y):
return ans
for a, b in dirs:
c, d = i + a, j + b
if (c, d) not in vis:
vis.add((c, d))
q.append((c, d))
ans += 1
return -1Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1197. Minimum Knight Moves is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Breadth-First Search.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0102 | Binary Tree Level Order Traversal | Medium |
| 0103 | Binary Tree Zigzag Level Order Traversal | Medium |
| 0107 | Binary Tree Level Order Traversal II | Medium |
| 0429 | N-ary Tree Level Order Traversal | Medium |
| 0864 | Shortest Path to Get All Keys | Hard |
| 0909 | Snakes and Ladders | Medium |
Frequently asked questions
- How hard is LeetCode 1197. Minimum Knight Moves?
LeetCode 1197. Minimum Knight Moves is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1197. Minimum Knight Moves?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1197. Minimum Knight Moves?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1197. Minimum Knight Moves cover?
LeetCode 1197. Minimum Knight Moves is tagged Breadth-First Search on LeetCode.
- Is LeetCode 1197. Minimum Knight Moves a premium problem?
Yes. LeetCode 1197. Minimum Knight Moves is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.