⚡Flashcard Drill➔
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

  1. This is a reachability problem; a BFS over indices works, but a naive one re-scans the same range many times.
  2. Keep far, the furthest index already enqueued, so each index is pushed at most once.
  3. From index i, the candidate window is [max(i + minJump, far + 1), min(i + maxJump, n - 1)].
  4. Enqueue every 0 in 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); the far pointer prevents this.
  • Forgetting s[-1] == '1': a 1 at the target can never be landed on, so the answer is immediately false.
  • Landing on a 1: only 0 indices 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems