LeetCode 1871 - Jump Game VII

The problem gives us a binary string s, where each character is either '0' or '1'. We start at index 0, and the problem guarantees that s[0] == '0', meaning the starting position is always valid.

leetcodemediumstringdynamic-programmingsliding-windowprefix-sum

LeetCode Problem 1871

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem gives us a binary string s, where each character is either '0' or '1'. We start at index 0, and the problem guarantees that s[0] == '0', meaning the starting position is always valid.

From any index i, we are allowed to jump to another index j if two conditions hold:

  1. The jump distance is within the allowed range:

i + minJump <= j <= i + maxJump 2. The destination position must contain '0'.

The goal is to determine whether it is possible to eventually reach the last index of the string.

In other words, we are navigating through the string while only landing on positions containing '0', and every jump length must stay within the inclusive interval [minJump, maxJump].

The constraints are extremely important:

  • s.length can be as large as 10^5
  • A naive graph traversal that checks every possible jump from every index could become quadratic
  • An O(n^2) solution will time out

This means we need an algorithm that processes the string efficiently, ideally in linear time.

A few important observations emerge immediately:

  • We never need to land on indices containing '1'
  • Reachability matters more than the exact path
  • For every position, we need to know whether there exists at least one previously reachable index that can jump to it
  • Repeatedly scanning large ranges would be too expensive

Several edge cases can easily break naive implementations:

  • The last index may contain '1', making the answer automatically false
  • Large jump ranges may cause repeated redundant scanning
  • Some indices may technically be within range but unreachable themselves
  • Consecutive '1' blocks can completely isolate parts of the string
  • Very small strings can expose off-by-one mistakes

The problem guarantees:

  • The string length is at least 2
  • minJump <= maxJump
  • The start index is always valid

These guarantees simplify initialization logic.

Approaches

Brute Force Approach

A straightforward solution is to model the problem as a graph traversal problem.

Each index represents a node. From index i, we try every possible jump length between minJump and maxJump. If the destination index contains '0', we recursively or iteratively continue exploring from there.

This can be implemented using either DFS or BFS.

The approach is correct because it explores every reachable position and checks whether the final index can be visited.

However, the performance is poor.

For each index, we may examine up to maxJump - minJump + 1 destinations. In the worst case, this becomes approximately O(n) work per index, producing an overall complexity of O(n^2).

With n = 100000, quadratic behavior is far too slow.

Key Insight for the Optimal Solution

The expensive part of the brute force solution is repeatedly scanning overlapping jump ranges.

Suppose we want to determine whether index i is reachable.

Instead of checking every earlier index individually, we only need to know this:

Does there exist at least one reachable index inside the valid jump window for i?

For index i, the valid previous indices are:

[i - maxJump, i - minJump]

If any reachable position exists inside this interval, then i is reachable, provided s[i] == '0'.

This becomes a classic sliding window problem.

We maintain a running count of how many reachable indices currently exist inside the valid range. As we move through the string from left to right:

  • We add indices entering the window
  • We remove indices leaving the window
  • We check whether the count is positive

This avoids rescanning the same ranges repeatedly.

The result is a linear time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Tries all possible jumps from every reachable index
Optimal Sliding Window DP O(n) O(n) Maintains reachable indices using a moving window

Algorithm Walkthrough

Step 1: Create a DP Array

We create a boolean array reachable of size n.

reachable[i] means:

Can we reach index i?

Initialize:

  • reachable[0] = True
  • Every other position starts as False

We know index 0 is reachable because that is the starting position.

Step 2: Maintain a Sliding Window Count

We maintain an integer variable called window_reachable.

This stores:

How many reachable indices currently exist inside the valid jump window?

For each position i, the valid previous indices are:

[i - maxJump, i - minJump]

Instead of rescanning this range every time, we update the count incrementally.

Step 3: Expand the Window

As we iterate from left to right:

When index i - minJump becomes valid, it enters the window.

If that index is reachable, we increment window_reachable.

if reachable[i - minJump]:
    window_reachable += 1

This means future positions can potentially jump from it.

Step 4: Shrink the Window

When index i - maxJump - 1 moves out of range, it leaves the window.

If that index was reachable, we decrement the count.

if reachable[i - maxJump - 1]:
    window_reachable -= 1

This keeps the window accurate.

Step 5: Determine Reachability

Now we check the current index i.

It is reachable if:

  1. s[i] == '0'
  2. There exists at least one reachable index in the window

The second condition becomes:

window_reachable > 0

So:

reachable[i] = (s[i] == '0' and window_reachable > 0)

Step 6: Return Final Result

At the end, return:

reachable[n - 1]

This tells us whether the last index can be reached.

Why it works

The algorithm maintains the invariant that window_reachable always equals the number of reachable indices inside the valid jump interval for the current position.

For each index i, the only way to reach it is from a previously reachable index inside:

[i - maxJump, i - minJump]

The sliding window ensures we always know whether such an index exists in constant time. Since every index is processed exactly once, the algorithm correctly computes reachability for the entire string.

Python Solution

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)

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

        window_reachable = 0

        for i in range(1, n):
            enter_index = i - minJump
            if enter_index >= 0 and reachable[enter_index]:
                window_reachable += 1

            leave_index = i - maxJump - 1
            if leave_index >= 0 and reachable[leave_index]:
                window_reachable -= 1

            reachable[i] = (
                s[i] == '0' and window_reachable > 0
            )

        return reachable[-1]

The implementation follows the sliding window dynamic programming strategy directly.

The reachable array stores whether each position can be visited. Initially, only index 0 is reachable.

The variable window_reachable tracks how many reachable indices currently exist inside the valid jump interval for the current position.

For every index:

  • enter_index is the new index entering the sliding window
  • leave_index is the old index leaving the window

Whenever a reachable index enters the window, the count increases. Whenever one leaves, the count decreases.

After updating the window, the current position becomes reachable if:

  • The character is '0'
  • At least one reachable index exists in the current valid range

Finally, the algorithm returns whether the final index is reachable.

Go Solution

func canReach(s string, minJump int, maxJump int) bool {
    n := len(s)

    reachable := make([]bool, n)
    reachable[0] = true

    windowReachable := 0

    for i := 1; i < n; i++ {
        enterIndex := i - minJump
        if enterIndex >= 0 && reachable[enterIndex] {
            windowReachable++
        }

        leaveIndex := i - maxJump - 1
        if leaveIndex >= 0 && reachable[leaveIndex] {
            windowReachable--
        }

        reachable[i] = s[i] == '0' && windowReachable > 0
    }

    return reachable[n-1]
}

The Go implementation is nearly identical to the Python version.

A boolean slice is used instead of a Python list. Go strings are indexable by byte, so checking s[i] == '0' works directly because the string contains only ASCII characters.

No special overflow handling is necessary because all indices remain within standard integer bounds for the given constraints.

Worked Examples

Example 1

Input:
s = "011010"
minJump = 2
maxJump = 3

Initial state:

Index 0 1 2 3 4 5
s[i] 0 1 1 0 1 0

Initial DP:

Index 0 1 2 3 4 5
reachable T F F F F F

Now iterate through the string.

i enterIndex leaveIndex windowReachable s[i] reachable[i]
1 -1 -3 0 1 False
2 0 -2 1 1 False
3 1 -1 1 0 True
4 2 0 0 1 False
5 3 1 1 0 True

Final result:

reachable[5] = True

Answer:

true

Example 2

Input:
s = "01101110"
minJump = 2
maxJump = 3

Initial state:

Index 0 1 2 3 4 5 6 7
s[i] 0 1 1 0 1 1 1 0

Iteration table:

i enterIndex leaveIndex windowReachable s[i] reachable[i]
1 -1 -3 0 1 False
2 0 -2 1 1 False
3 1 -1 1 0 True
4 2 0 0 1 False
5 3 1 1 1 False
6 4 2 1 1 False
7 5 3 0 0 False

Final result:

reachable[7] = False

Answer:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index enters and leaves the sliding window once
Space O(n) The reachability DP array stores one boolean per index

The algorithm processes the string in a single left to right pass. Every index contributes to the sliding window at most once when entering and once when leaving. No nested rescanning occurs, which guarantees linear time complexity.

The extra memory comes from the reachable array used to store computed reachability states.

Test Cases

solution = Solution()

# Provided examples
assert solution.canReach("011010", 2, 3) == True  # reachable path exists
assert solution.canReach("01101110", 2, 3) == False  # destination blocked logically

# Smallest valid size
assert solution.canReach("00", 1, 1) == True  # direct jump to end

# End is unreachable due to '1'
assert solution.canReach("01", 1, 1) == False  # cannot land on final index

# Consecutive zeros
assert solution.canReach("00000", 1, 2) == True  # many possible paths

# Large blocked segment
assert solution.canReach("0001111000", 2, 3) == False  # blocked middle prevents progress

# Exact jump required
assert solution.canReach("01000", 2, 2) == True  # must use exact jump length

# Reachable only through specific path
assert solution.canReach("0000000", 2, 3) == True  # multiple overlapping paths

# Impossible due to jump constraints
assert solution.canReach("0000000", 4, 5) == False  # cannot chain jumps correctly

# Single valid route
assert solution.canReach("0100010", 2, 3) == True  # only one effective sequence

# Dense obstacles
assert solution.canReach("0011100110", 2, 5) == True  # requires skipping blocked regions

# Large continuous reachable area
assert solution.canReach("0" * 1000, 1, 10) == True  # stress test for performance

Test Case Summary

Test Why
"011010", 2, 3 Validates the basic reachable scenario
"01101110", 2, 3 Validates unreachable destination
"00", 1, 1 Smallest valid input
"01", 1, 1 Final index cannot be landed on
"00000", 1, 2 Multiple possible paths
"0001111000", 2, 3 Blocked region prevents continuation
"01000", 2, 2 Requires exact jump lengths
"0000000", 2, 3 Verifies overlapping reachable windows
"0000000", 4, 5 Tests jump constraint limitations
"0100010", 2, 3 Validates narrow valid routing
"0011100110", 2, 5 Tests skipping obstacle clusters
"0" * 1000, 1, 10 Stress test for linear performance

Edge Cases

One important edge case occurs when the final index contains '1'. Even if every earlier position is reachable, the last position cannot be landed on because jumps are only allowed onto '0' cells. The implementation handles this naturally because reachable[i] is only set to True when s[i] == '0'.

Another subtle case involves large stretches of '1' characters that disconnect the graph. A naive implementation might repeatedly rescan these regions, causing severe performance degradation. The sliding window approach avoids this problem entirely because it only tracks the count of reachable indices inside the valid interval.

A third important edge case occurs when minJump == maxJump. In this situation, every move must use exactly one jump length. Many implementations accidentally assume a range of possibilities always exists. The sliding window still works correctly because the window simply collapses into a fixed-width interval of size one.

A final tricky case involves early indices where the sliding window boundaries become negative. Without careful bounds checks, implementations can accidentally access invalid indices. The solution explicitly checks >= 0 before using enterIndex or leaveIndex, preventing out-of-range access errors.