Jump Game VII

Description

You are given a 0-indexed binary string s (containing only '0's and '1's) and two integers minJump and maxJump. You start standing at index 0, which is guaranteed to be '0'.

From any index i, you can jump to an index j if all of the following conditions are met:

The jump distance is within the allowed range: i + minJump <= j <= min(i + maxJump, s.length - 1)
The destination has a '0': s[j] == '0'

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

In simpler terms: you are on a number line of 0s and 1s. You can only stand on 0s. From any position, you must jump forward by at least minJump and at most maxJump positions, landing on another 0. Can you reach the end?

Examples

Example 1

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

Output: true

Explanation: Starting at index 0 (which is '0'), we can jump to index 3 (distance 3, within [2, 3] range, and s[3] = '0'). From index 3, we can jump to index 5 (distance 2, within [2, 3] range, and s[5] = '0'). Index 5 is the last index, so we return true. The path is: 0 → 3 → 5.

Example 2

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

Output: false

Explanation: From index 0, we can jump to indices 2 or 3. Index 2 has '1' (blocked), so we can only reach index 3 (s[3] = '0'). From index 3, we can jump to indices 5 or 6. Index 5 has '1' and index 6 has '1' — both blocked. We're stuck at index 3 with no way to proceed. The last index (7) is unreachable.

Example 3

Input: s = "0000000000", minJump = 1, maxJump = 5

Output: true

Explanation: All positions are '0' and we can jump 1 to 5 steps forward. Many paths exist to reach the end. For instance: 0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9.

Constraints

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

Editorial

Brute Force

Intuition

The most natural way to think about this problem is as a reachability check: for each position in the string, determine whether it can be reached from any previously reachable position.

Imagine you are hopping across stepping stones in a river. Some stones are safe ('0') and some are submerged ('1'). You can only jump forward by a distance between minJump and maxJump. To check if a stone is reachable, you look back at all stones within jumping distance and ask: 'Is any of those stones reachable and safe?'

We create a boolean array reachable where reachable[i] means 'can I reach position i?'. Position 0 is always reachable. For each subsequent position i where s[i] == '0', we check every position j in the range [max(0, i - maxJump), i - minJump]. If any such j has reachable[j] == true, then position i is also reachable.

This straightforward approach works correctly but is slow because for each position we may scan a large range of previous positions.

Step-by-Step Explanation

Let's trace through s = "011010", minJump = 2, maxJump = 3:

Step 1: Initialize reachable = [true, false, false, false, false, false]. Position 0 is our starting point.

Step 2: i=1, s[1]='1'. Cannot land on '1'. reachable[1] = false.

Step 3: i=2, s[2]='1'. Cannot land on '1'. reachable[2] = false.

Step 4: i=3, s[3]='0'. Can potentially land here. Check which positions can jump to index 3:

Range: [max(0, 3-3), 3-2] = [0, 1]
j=0: reachable[0] = true! Found a reachable source.
Set reachable[3] = true.

Step 5: i=4, s[4]='1'. Cannot land on '1'. reachable[4] = false.

Step 6: i=5, s[5]='0'. Can potentially land here. Check range:

Range: [max(0, 5-3), 5-2] = [2, 3]
j=2: reachable[2] = false. Not a source.
j=3: reachable[3] = true! Found a reachable source.
Set reachable[5] = true.

Step 7: Position 5 is the last index and reachable[5] = true. Return true.

Notice in Step 6, we scanned through positions 2 and 3 to find a reachable source. In the worst case, this inner scan covers up to (maxJump - minJump + 1) positions per index.

Brute Force DP — Scanning Back to Check Reachability — Watch how for each '0' position, we scan backward through the jumping range to find any reachable source position. The backward scan is the expensive part.

Algorithm

Create a boolean array reachable of size n, initialized to false
Set reachable[0] = true (starting position)
For each index i from 1 to n-1:
a. If s[i] == '1', skip (cannot land on '1')
b. Compute source range: left = max(0, i - maxJump), right = i - minJump
c. If right < 0, skip (no valid source range)
d. For each j from left to right:
- If reachable[j] == true, set reachable[i] = true and break
Return reachable[n-1]

Code

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<bool> reachable(n, false);
        reachable[0] = true;
        
        for (int i = 1; i < n; i++) {
            if (s[i] == '1') continue;
            
            int left = max(0, i - maxJump);
            int right = i - minJump;
            if (right < 0) continue;
            
            for (int j = left; j <= right; j++) {
                if (reachable[j]) {
                    reachable[i] = true;
                    break;
                }
            }
        }
        
        return reachable[n - 1];
    }
};

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        reachable = [False] * n
        reachable[0] = True
        
        for i in range(1, n):
            if s[i] == '1':
                continue
            
            left = max(0, i - maxJump)
            right = i - minJump
            if right < 0:
                continue
            
            for j in range(left, right + 1):
                if reachable[j]:
                    reachable[i] = True
                    break
        
        return reachable[n - 1]

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        boolean[] reachable = new boolean[n];
        reachable[0] = true;
        
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '1') continue;
            
            int left = Math.max(0, i - maxJump);
            int right = i - minJump;
            if (right < 0) continue;
            
            for (int j = left; j <= right; j++) {
                if (reachable[j]) {
                    reachable[i] = true;
                    break;
                }
            }
        }
        
        return reachable[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n × (maxJump - minJump))

For each of the n positions, the inner loop scans up to (maxJump - minJump + 1) positions. In the worst case where all positions are '0' and the jump range is wide (e.g., maxJump ≈ n), this becomes O(n²).

Space Complexity: O(n)

We use a boolean array reachable of size n to track which positions are reachable.

Why This Approach Is Not Efficient

The brute force approach has a nested loop structure: for each position i, we scan up to (maxJump - minJump + 1) positions backward. With n up to 10^5 and potentially wide jump ranges, this can lead to ~10^10 operations — far too slow.

The fundamental problem is that we're answering the same question repeatedly: 'Is there any reachable position in the range [left, right]?' Each time, we scan the entire range from scratch. But we're building the reachable array incrementally left-to-right, so the information accumulates.

Key insight: instead of scanning the range each time, we can precompute a prefix sum of the reachable array. A prefix sum lets us answer 'how many reachable positions exist in range [l, r]?' in O(1) time by computing prefix[r+1] - prefix[l]. If this count is greater than 0, position i is reachable.

Better Approach - BFS with Sliding Window

Intuition

Instead of DP, we can view this as a graph problem. Each index with '0' is a node, and there is an edge from node i to node j if j is within the jump range of i and s[j] == '0'. We want to find if there is a path from node 0 to node n-1.

A BFS (Breadth-First Search) naturally solves reachability problems. Start from index 0, enqueue all reachable '0' positions within its jump range, then process each dequeued position the same way.

The naive BFS would be just as slow as brute force if we re-enqueue positions already processed. The trick is to maintain a boundary pointer farthest that tracks the furthest index we have already considered for enqueueing. When processing position i, instead of scanning the full range [i + minJump, i + maxJump], we only scan from max(i + minJump, farthest + 1) to i + maxJump. After processing, we update farthest = max(farthest, i + maxJump).

This ensures every index is considered for enqueueing at most once, giving us O(n) total work.

Step-by-Step Explanation

Let's trace through s = "011010", minJump = 2, maxJump = 3:

Step 1: Initialize queue = [0], farthest = 0. Start BFS from index 0.

Step 2: Dequeue index 0. Jump range: [0+2, min(0+3, 5)] = [2, 3].

Since farthest=0, scan from max(2, 0+1)=2 to 3.
j=2: s[2]='1'. Blocked. Don't enqueue.
j=3: s[3]='0'. Enqueue 3.
Update farthest = max(0, 3) = 3.
Queue = [3].

Step 3: Dequeue index 3. Jump range: [3+2, min(3+3, 5)] = [5, 5].

Since farthest=3, scan from max(5, 3+1)=5 to 5.
j=5: s[5]='0'. Enqueue 5.
Update farthest = max(3, 5) = 5.
Queue = [5].

Step 4: Dequeue index 5. This is the last index! Return true.

The farthest pointer ensures we never re-examine the same index twice across all BFS levels.

BFS with Sliding Window — Level-by-Level Exploration — Watch how BFS explores reachable positions level by level, using a boundary pointer to avoid re-processing indices already considered.

Algorithm

If s[n-1] == '1', return false (last position blocked)
Initialize a queue with index 0, set farthest = 0
While the queue is not empty:
a. Dequeue position curr
b. If curr == n-1, return true
c. Compute scan range: start = max(curr + minJump, farthest + 1), end = min(curr + maxJump, n - 1)
d. For j from start to end:
- If s[j] == '0', enqueue j
  e. Update farthest = max(farthest, curr + maxJump)
Return false (queue exhausted without reaching end)

Code

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        if (s[n - 1] == '1') return false;
        
        queue<int> q;
        q.push(0);
        int farthest = 0;
        
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            
            if (curr == n - 1) return true;
            
            int start = max(curr + minJump, farthest + 1);
            int end = min(curr + maxJump, n - 1);
            
            for (int j = start; j <= end; j++) {
                if (s[j] == '0') {
                    q.push(j);
                }
            }
            farthest = max(farthest, curr + maxJump);
        }
        
        return false;
    }
};

from collections import deque

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[n - 1] == '1':
            return False
        
        queue = deque([0])
        farthest = 0
        
        while queue:
            curr = queue.popleft()
            
            if curr == n - 1:
                return True
            
            start = max(curr + minJump, farthest + 1)
            end = min(curr + maxJump, n - 1)
            
            for j in range(start, end + 1):
                if s[j] == '0':
                    queue.append(j)
            
            farthest = max(farthest, curr + maxJump)
        
        return False

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        if (s.charAt(n - 1) == '1') return false;
        
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        int farthest = 0;
        
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            
            if (curr == n - 1) return true;
            
            int start = Math.max(curr + minJump, farthest + 1);
            int end = Math.min(curr + maxJump, n - 1);
            
            for (int j = start; j <= end; j++) {
                if (s.charAt(j) == '0') {
                    queue.offer(j);
                }
            }
            farthest = Math.max(farthest, curr + maxJump);
        }
        
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each index is visited at most once in the inner for-loop thanks to the farthest pointer. The pointer only moves forward, and once an index has been scanned, it is never scanned again. Over all BFS iterations combined, the total number of inner-loop steps is at most n.

Space Complexity: O(n)

The BFS queue can hold up to n positions in the worst case (if all positions are '0' and reachable). No additional arrays are needed beyond the queue.

Why This Approach Is Not Efficient

The BFS approach is already O(n) time and O(n) space, which is optimal for this problem. However, the BFS approach has a practical downside: the queue can grow large (up to n elements) and the graph-traversal framework introduces overhead from enqueue/dequeue operations.

A more elegant and typically faster-in-practice solution uses Dynamic Programming with Prefix Sum. Instead of BFS with a boundary pointer, we maintain a prefix sum array that counts how many reachable positions exist up to each index. This lets us answer 'is there any reachable position in the jump source range?' in O(1) with a single subtraction, eliminating the need for a queue entirely.

The DP approach is conceptually cleaner: it processes positions strictly left-to-right with no queue management, and it separates the 'counting reachable sources' step from the 'marking reachable positions' step using prefix sums.

Optimal Approach - DP with Prefix Sum

Intuition

The brute force DP's bottleneck was answering 'is there any reachable position in range [left, right]?' by scanning every position in that range. The key insight is that we can answer this query in O(1) time using a prefix sum.

Imagine you have a row of switches, some ON (reachable) and some OFF (unreachable). To check if ANY switch in a range is ON, you could count them one by one (brute force), or you could maintain a running count: 'how many switches are ON up to position k?' Then the number of ON switches in range [l, r] is just count_up_to[r] - count_up_to[l-1]. If this is greater than 0, at least one switch in the range is ON.

This is exactly what a prefix sum does. We define:

f[i] = true if position i is reachable
pre[i] = number of reachable positions in the first i positions (prefix sum of f)

For each position i with s[i] == '0', the source range is [l, r] where l = max(0, i - maxJump) and r = i - minJump. Position i is reachable if pre[r+1] - pre[l] > 0, which we compute in O(1).

We build the f and pre arrays simultaneously from left to right, so by the time we process position i, all positions before it have already been resolved.

Step-by-Step Explanation

Let's trace through s = "011010", minJump = 2, maxJump = 3:

Step 1: Initialize f = [true, false, false, false, false, false], pre = [0, 1, 0, 0, 0, 0, 0] (size n+1). pre[1] = 1 because position 0 is reachable.

Step 2: i=1, s[1]='1'. Cannot land on '1'. f[1] = false. pre[2] = pre[1] + 0 = 1.

Step 3: i=2, s[2]='1'. Cannot land on '1'. f[2] = false. pre[3] = pre[2] + 0 = 1.

Step 4: i=3, s[3]='0'. Compute source range: l = max(0, 3-3) = 0, r = 3-2 = 1.

l ≤ r? Yes (0 ≤ 1).
Count reachable in [0, 1]: pre[r+1] - pre[l] = pre[2] - pre[0] = 1 - 0 = 1 > 0.
At least one reachable position exists in the source range!
f[3] = true. pre[4] = pre[3] + 1 = 2.

Step 5: i=4, s[4]='1'. Cannot land on '1'. f[4] = false. pre[5] = pre[4] + 0 = 2.

Step 6: i=5, s[5]='0'. Compute source range: l = max(0, 5-3) = 2, r = 5-2 = 3.

l ≤ r? Yes (2 ≤ 3).
Count reachable in [2, 3]: pre[r+1] - pre[l] = pre[4] - pre[2] = 2 - 1 = 1 > 0.
f[5] = true. pre[6] = pre[5] + 1 = 3.

Step 7: Return f[5] = true. The last index is reachable!

Notice that each step was O(1) — no inner loop, just a single prefix sum query.

DP with Prefix Sum — O(1) Range Queries for Reachability — Watch how the prefix sum array lets us check reachability of any range in constant time. The f array and pre array build simultaneously left-to-right.

Algorithm

Initialize boolean array f of size n with f[0] = true
Initialize prefix sum array pre of size n+1 with pre[1] = 1
For each index i from 1 to n-1:
a. If s[i] == '0':
- Compute left = max(0, i - maxJump), right = i - minJump
- If left <= right and pre[right + 1] - pre[left] > 0:
  - Set f[i] = true
    b. Update pre[i + 1] = pre[i] + (1 if f[i] else 0)
Return f[n - 1]

Code

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<bool> f(n, false);
        f[0] = true;
        
        // pre[i] = number of reachable positions in first i positions
        vector<int> pre(n + 1, 0);
        pre[1] = 1;
        
        for (int i = 1; i < n; i++) {
            if (s[i] == '0') {
                int left = max(0, i - maxJump);
                int right = i - minJump;
                
                if (left <= right && pre[right + 1] - pre[left] > 0) {
                    f[i] = true;
                }
            }
            pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
        }
        
        return f[n - 1];
    }
};

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        f = [False] * n
        f[0] = True
        
        # pre[i] = count of reachable positions in first i positions
        pre = [0] * (n + 1)
        pre[1] = 1
        
        for i in range(1, n):
            if s[i] == '0':
                left = max(0, i - maxJump)
                right = i - minJump
                
                if left <= right and pre[right + 1] - pre[left] > 0:
                    f[i] = True
            
            pre[i + 1] = pre[i] + (1 if f[i] else 0)
        
        return f[n - 1]

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        boolean[] f = new boolean[n];
        f[0] = true;
        
        // pre[i] = count of reachable positions in first i positions
        int[] pre = new int[n + 1];
        pre[1] = 1;
        
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '0') {
                int left = Math.max(0, i - maxJump);
                int right = i - minJump;
                
                if (left <= right && pre[right + 1] - pre[left] > 0) {
                    f[i] = true;
                }
            }
            pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
        }
        
        return f[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once. At each position, we perform O(1) work: one character comparison, one range computation (two max operations), one prefix sum query (one subtraction and comparison), and one prefix sum update (one addition). Total: O(n).

Space Complexity: O(n)

We use a boolean array f of size n and a prefix sum array pre of size n+1. Both are O(n). Unlike the BFS approach, there is no queue overhead — just two flat arrays accessed sequentially, which is cache-friendly and fast in practice.

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Jump Game VII

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - BFS with Sliding Window

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - DP with Prefix Sum

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis