Jump Game VII

Difficulty: Medium Source: NeetCode

Problem

You are given a binary string s (only '0' and '1'), and two integers minJump and maxJump. Start at index 0 (which is always '0'). On each move, jump from index i to any index j where i + minJump <= j <= i + maxJump and s[j] == '0'. Return true if you can reach index n - 1.

Example 1: Input: s = "011010", minJump = 2, maxJump = 3 Output: true Explanation: Jump from index 0 → 3 → 5.

Example 2: Input: s = "01101110", minJump = 2, maxJump = 3 Output: false

Constraints:

• 2 <= s.length <= 10^5
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

Prerequisites

Before attempting this problem, you should be comfortable with:

• Jump Game I & II — simpler jump variants
• Prefix sums — counting elements in a range efficiently
• Sliding window — maintaining a running count over a window

1. Brute Force / BFS

Intuition

Do a BFS from index 0. At each reachable index i that contains '0', add all indices j in [i + minJump, i + maxJump] that also contain '0' and haven’t been visited. Return true if we ever reach n - 1.

Algorithm

1. Start BFS from {0}.
2. For each reachable index i, explore j from i + minJump to i + maxJump.
3. Add unvisited '0' indices to the next level.
4. Return True if n-1 is reached.

Solution

from collections import deque

def canReach(s, minJump, maxJump):
    n = len(s)
    if s[-1] == '1':
        return False

    visited = {0}
    queue = deque([0])

    while queue:
        i = queue.popleft()
        for j in range(i + minJump, min(i + maxJump + 1, n)):
            if j not in visited and s[j] == '0':
                if j == n - 1:
                    return True
                visited.add(j)
                queue.append(j)

    return (n - 1) in visited


print(canReach("011010", 2, 3))     # True
print(canReach("01101110", 2, 3))   # False
print(canReach("00", 1, 1))         # True

Complexity

• Time: O(n * maxJump) — slow when window is large
• Space: O(n)

2. Greedy — Sliding Window with Prefix Reachability

Intuition

Use a boolean array reachable[i] = can we reach index i. reachable[0] = True. For each index j (where s[j] == '0'), it’s reachable if any index in [j - maxJump, j - minJump] is reachable.

Naively checking this range is O(n * maxJump). To speed it up, maintain a running count of reachable indices in a sliding window. Use a prefix sum (or an integer counter updated as the window slides).

Algorithm

1. reachable = [False] * n, reachable[0] = True.
2. window_count = 0 — count of reachable positions in the current window.
3. For j from 1 to n-1:
   • If j - minJump >= 0 and reachable[j - minJump]: increment window_count.
   • If j - maxJump - 1 >= 0 and reachable[j - maxJump - 1]: decrement window_count.
   • If s[j] == '0' and window_count > 0: reachable[j] = True.
4. Return reachable[n-1].

Solution

def canReach(s, minJump, maxJump):
    n = len(s)
    if s[-1] == '1':
        return False

    reachable = [False] * n
    reachable[0] = True
    window_count = 0  # reachable positions in [j - maxJump, j - minJump]

    for j in range(1, n):
        # Add left boundary entering the window
        if j >= minJump and reachable[j - minJump]:
            window_count += 1
        # Remove element leaving the window from the right
        if j > maxJump and reachable[j - maxJump - 1]:
            window_count -= 1
        # Mark j reachable if it's '0' and there's a valid predecessor
        if s[j] == '0' and window_count > 0:
            reachable[j] = True

    return reachable[n - 1]


print(canReach("011010", 2, 3))     # True
print(canReach("01101110", 2, 3))   # False
print(canReach("00", 1, 1))         # True
print(canReach("0000000000", 2, 3)) # True


# Alternatively, using prefix sums
def canReach_prefix(s, minJump, maxJump):
    n = len(s)
    if s[-1] == '1':
        return False

    reachable = [0] * (n + 1)  # prefix sum of reachable flags
    reachable[1] = 1  # index 0 is reachable (1-indexed prefix)

    dp = [False] * n
    dp[0] = True

    for j in range(1, n):
        if s[j] == '0':
            lo = max(0, j - maxJump)
            hi = j - minJump
            if hi >= 0 and reachable[hi + 1] - reachable[lo] > 0:
                dp[j] = True
        reachable[j + 1] = reachable[j] + (1 if dp[j] else 0)

    return dp[n - 1]


print(canReach_prefix("011010", 2, 3))     # True
print(canReach_prefix("01101110", 2, 3))   # False

Complexity

• Time: O(n)
• Space: O(n)

Common Pitfalls

Sliding the window incorrectly. The window for position j is [j - maxJump, j - minJump]. When we process j, we add the incoming element j - minJump and remove the outgoing element j - maxJump - 1. Off-by-one here is very easy.

Not checking s[-1] == '1' early. If the last position is '1', we can never land there — short-circuit immediately.

Using BFS when maxJump is large. The BFS approach is O(n * maxJump), which can be O(n²) in the worst case. The sliding window / prefix sum approach is strictly O(n).