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.

Minimum Knight Moves — LeetCode 1197 Python Solution

MediumLeetCode PremiumBreadth-First Search

Problem: #1197
Pattern: 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

Python

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 -1

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

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.

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.