1871. Jump Game VII

String
Dynamic Programming
Prefix Sum
Sliding Window

TIME

O(n)

SPACE

O(n)

Intuition

Let reachable[i] mean index i can be reached from index 0.

For an index i, the possible previous indices are:

i - maxJump <= previous <= i - minJump

So i is reachable if s[i] == '0' and at least one index in that previous range is already reachable.

Checking that whole range for every index would be too slow. Instead, keep a sliding count of reachable previous indices that are currently allowed to jump into i.

Approach

Set reachable[0] = true.
Iterate i from 1 to n - 1.
Add reachable[i - minJump] into the sliding window when that index becomes close enough to jump to i.
Remove reachable[i - maxJump - 1] when that index becomes too far away.
If s[i] == '0' and the sliding count is greater than 0, mark reachable[i] = true.
Return reachable[n - 1].

Complexity

Time: O(n), each index enters and leaves the sliding window once
Space: O(n), for the reachable array

Edge Cases

Last index is '1' -> cannot be reached
minJump == maxJump -> the window has at most one jump distance
Long runs of '1' -> reachable count may be positive, but landing is still blocked
Large input -> avoids O(n * jumpRange) scanning

Code

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        """
        1871. Jump Game VII
        Time: O(n)
        Space: O(n)
        """
        n = len(s)
        reachable = [False] * n
        reachable[0] = True
        reachable_count = 0

        for index in range(1, n):
            add_index = index - minJump
            if add_index >= 0 and reachable[add_index]:
                reachable_count += 1

            remove_index = index - maxJump - 1
            if remove_index >= 0 and reachable[remove_index]:
                reachable_count -= 1

            reachable[index] = s[index] == "0" and reachable_count > 0

        return reachable[-1]

/**
 * 1871. Jump Game VII
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        boolean[] reachable = new boolean[n];
        reachable[0] = true;
        int reachableCount = 0;

        for (int index = 1; index < n; index++) {
            int addIndex = index - minJump;
            if (addIndex >= 0 && reachable[addIndex]) {
                reachableCount++;
            }

            int removeIndex = index - maxJump - 1;
            if (removeIndex >= 0 && reachable[removeIndex]) {
                reachableCount--;
            }

            reachable[index] = s.charAt(index) == '0' && reachableCount > 0;
        }

        return reachable[n - 1];
    }
}