NeetCode #782LC-1871MediumGreedyNC 250
← Back to All Problems#782 · #1871 · Jump Game VII(跳跃游戏 VII)
📌 Problem Statement & Constraints
Given a 0-indexed binary string
s, and integers minJump and maxJump, you start at index 0 and may jump from i to j if s[j] == '0' and minJump <= j - i <= maxJump. Return whether you can reach n - 1. Constraints: 2 <= s.length <= 10^5, 0 <= minJump <= maxJump < s.length, s[0] == '0'.💡 Core Algorithmic Approaches
- This is a reachability problem; a BFS over indices works, but a naive one re-scans the same range many times.
- Keep
far, the furthest index already enqueued, so each index is pushed at most once. - From index
i, the candidate window is[max(i + minJump, far + 1), min(i + maxJump, n - 1)]. - Enqueue every
0in that window; if the last index is ever enqueued, return true.
💻 Benchmark Python3 Implementation
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
from collections import deque
n = len(s)
if s[-1] == "1":
return False
q = deque([0])
far = 0 # furthest index already enqueued
while q:
i = q.popleft()
lo = max(i + minJump, far + 1)
hi = min(i + maxJump, n - 1)
for j in range(lo, hi + 1):
if s[j] == "0":
if j == n - 1:
return True
q.append(j)
far = max(far, hi)
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is enqueued and scanned at most once thanks to far.
💾 Space Complexity
O(n): the queue and the reachable-index bookkeeping.
⚠️ Interview Pitfalls & Follow-ups
- Scanning
[i + minJump, i + maxJump]for every dequeued index: the same indices get revisited and the worst case degrades to O(n^2); thefarpointer prevents this. - Forgetting
s[-1] == '1': a1at the target can never be landed on, so the answer is immediately false. - Landing on a
1: only0indices are valid landing spots. - Starting the window below
far + 1: it re-enqueues indices already processed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.