Minimum Jumps to Reach Home — LeetCode 1654 Python Solution
MediumBreadth-First SearchArrayDynamic Programming
- Problem
- #1654
- Pattern
- Breadth-First Search
- Reading time
- 4 min
- Source
- leetcode.com
The problem
A certain bug's home is on the x-axis at position x. Help them get there from position 0.
Example
- Input
- forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
- Output
- 3
- Explanation
- 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.
Python solution
Python
class Solution:
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
s = set(forbidden)
q = deque([(0, 1)])
vis = {(0, 1)}
ans = 0
while q:
for _ in range(len(q)):
i, k = q.popleft()
if i == x:
return ans
nxt = [(i + a, 1)]
if k & 1:
nxt.append((i - b, 0))
for j, k in nxt:
if 0 <= j < 6000 and j not in s and (j, k) not in vis:
q.append((j, k))
vis.add((j, k))
ans += 1
return -1Complexity
| Measure | Complexity |
|---|---|
| Time | O(M) |
| Space | O(M) auxiliary |
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1654. Minimum Jumps to Reach Home is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1654. Minimum Jumps to Reach Home?
- LeetCode 1654. Minimum Jumps to Reach Home is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1654. Minimum Jumps to Reach Home?
- The Python solution on this page runs in O(M).
- What is the space complexity of LeetCode 1654. Minimum Jumps to Reach Home?
- The Python solution on this page uses O(M) auxiliary space.
- What topics does LeetCode 1654. Minimum Jumps to Reach Home cover?
- LeetCode 1654. Minimum Jumps to Reach Home is tagged Breadth-First Search, Array and Dynamic Programming on LeetCode.