1871. Jump Game VII

Problem Statement

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

i + minJump <= j <= min(i + maxJump, s.length - 1), and
s[j] == '0'

Return true if you can reach index s.length - 1 in s, or false otherwise.

Examples

Example 1

Input: s = "011010", minJump = 2, maxJump = 3
Output: true

Explanation: In the first step, move from index 0 to index 3. In the second step, move from index 3 to index 5.

Example 2

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

Constraints

2 <= s.length <= 10^5
s[i] is either '0' or '1'
s[0] == '0'
1 <= minJump <= maxJump < s.length

Explanation

Brute Force

DFS from each index. You are standing at index i, and from there you try jumping to every j where i + minJump <= j <= i + maxJump. If s[j] == '0' then you can move to that index, recurse into it. If you reach the last index return true, else return false.

But this isn’t fast enough, lets try to optimize.

Difference Array Technique

First I would like to explain this difference array technique for those who don’t know this.

Lets say you have an array of size n. You are given some ranges [l, r] and you want to add some value x to all the elements in that range, and you need to print the final array after all operations.

Lets optimize it later, but how will we do it at first place? For each given range [l, r], add x → for i = l to r, add x to arr[i]. This is O(n) for each query, and if you have q queries it will be O(q*n) which is too slow. But lets try to solve this in a different way.

Lets say we want to add 5 from index 0 to 4. Instead of updating each element, do a[0] += 5 and a[5] -= 5 (i.e., +x at a[l] and -x at a[r+1]). Then take a prefix sum of the array.

Our prefix array will look something like:

5 5 5 5 5 0 0 0 0 0

The +5 and -5 cancel out near a[5], so everything from index 0 to 4 carries the added value and everything after is back to 0. That’s the whole trick — we mark where the effect starts and where it ends, and a single prefix sum pass gives us the final state.

Note 1: This doesn’t work for live queries (alternating updates and queries). It works if you process all updates first and answer queries after.

Note 2: This generalizes to xor, add, subtract, etc.

Applying to this problem

If s.back() == '1' then we cannot reach it since we can only jump if s[i] == '0'.

If you can move to i then you can move to any j where j >= i + minJump and j <= i + maxJump and s[j] == '0'. Based on that, update the difference array and check if the last index is reachable.

Code

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<long long> pre(n);
        
        if (s.back() == '1') return false;
        pre[0] = 1;  pre[1] = -1;

        for (int i = 0; i < n; i++) {
            if (i)  pre[i] += pre[i - 1];

            int mnxt = min(i + minJump, n);
            int mxnxt = min(i + maxJump + 1, n);

            if (mnxt < n && s[i] == '0' and pre[i])
                pre[mnxt] += 1;
            if (mxnxt < n && s[i] == '0' and pre[i])
                pre[mxnxt] -= 1;
        }

        return pre[n - 1];
    }
};