Log inSign up
mediumLeetCodeNot Started

Jump Game VII

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

You are given a 0-indexed binary string s and two integers minJump and maxJump.

In the beginning, you are at index 0, which is guaranteed to be '0'. You can move from index i to index j if the following conditions are fulfilled: 1. i + minJump <= j <= min(i + maxJump, s.length - 1), and 2. s[j] == '0'.

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

### Example 1 - Input: s = "011010", minJump = 2, maxJump = 3 - Output: true - Explanation: - In the first step, move from index 0 to index 3 (0 + 3 = 3). - In the second step, move from index 3 to index 5 (3 + 2 = 5).

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

Constraints:

  • 2 <= s.length <= 105
  • s[i] is either 0 or 1
  • s[0] == 0
  • 1 <= minJump <= maxJump < s.length

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Optimize range-based DP transitions from O(window) to O(1) using sliding window.
  • Implement interval reachability counters.
  • Handle string boundary conditions and early termination.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Forward reachability with interval window [minJump, maxJump].
  • Large n = 100,000 requiring O(n) linear execution.

Algorithmic Decision Tree:

  • If last character s[n-1] == 1, immediately return false.
  • Use sliding window count over boolean reachability array.

Connected Patterns:

Jump GameJump Game IIVideo Stitching

1. Recursive Branching

Intuition

Recursively try jumping to every index j in [i + minJump, i + maxJump] where s[j] == 0.

Algorithm

  1. Define solve(i).
  2. If i == n - 1, return true.
  3. For j from i + minJump to min(i + maxJump, n - 1):
  4. If s[j] == '0' and solve(j) returns true, return true.
  5. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 bool solve(int i, const string& s, int minJump, int maxJump) {
9 if (i == s.length() - 1) return true;
10 int right = min((int)s.length() - 1, i + maxJump);
11 for (int j = i + minJump; j <= right; ++j) {
12 if (s[j] == '0' && solve(j, s, minJump, maxJump)) {
13 return true;
14 }
15 }
16 return false;
17 }
18public:
19 bool canReach(string s, int minJump, int maxJump) {
20 if (s.back() != '0') return false;
21 return solve(0, s, minJump, maxJump);
22 }
23};
24
25int main() {
26 Solution sol;
27 cout << (sol.canReach("011010", 2, 3) ? "true" : "false") << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^n)
  • Space complexity: O(n) call stack

2. Naive 1D DP (O(n * (maxJump - minJump)))

Intuition

Use a boolean array dp[n] and check all predecessor indices in range for each position.

Algorithm

  1. Initialize dp array of size n with false; dp[0] = true.
  2. For j from 1 to n - 1:
  3. If s[j] != '0', continue.
  4. For i from max(0, j - maxJump) to j - minJump:
  5. If dp[i] is true: dp[j] = true, break.
  6. Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 bool canReach(string s, int minJump, int maxJump) {
11 int n = s.length();
12 if (s[n - 1] != '0') return false;
13
14 vector<bool> dp(n, false);
15 dp[0] = true;
16
17 for (int j = 1; j < n; ++j) {
18 if (s[j] == '0') {
19 int left = max(0, j - maxJump);
20 int right = j - minJump;
21 for (int i = left; i <= right; ++i) {
22 if (dp[i]) {
23 dp[j] = true;
24 break;
25 }
26 }
27 }
28 }
29
30 return dp[n - 1];
31 }
32};
33
34int main() {
35 Solution sol;
36 cout << (sol.canReach("011010", 2, 3) ? "true" : "false") << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(n * (maxJump - minJump))
  • Space complexity: O(n)

3. Sliding Window Reachability Count (O(n) Time, O(n) Space)

Intuition

Maintain a sliding window counter reachableCount of reachable indices in range [j - maxJump, j - minJump] to evaluate each state in O(1).

Algorithm

  1. If s[n - 1] != '0', return false.
  2. Initialize boolean array dp of size n with false; dp[0] = true.
  3. reachableCount = 0.
  4. For j from 1 to n - 1:
  5. If j >= minJump && dp[j - minJump]: reachableCount++.
  6. If j > maxJump && dp[j - maxJump - 1]: reachableCount--.
  7. If s[j] == '0' && reachableCount > 0: dp[j] = true.
  8. Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8public:
9 bool canReach(string s, int minJump, int maxJump) {
10 int n = s.length();
11 if (s[n - 1] != '0') return false;
12
13 vector<bool> dp(n, false);
14 dp[0] = true;
15 int reachableCount = 0;
16
17 for (int j = 1; j < n; ++j) {
18 if (j >= minJump && dp[j - minJump]) {
19 reachableCount++;
20 }
21 if (j > maxJump && dp[j - maxJump - 1]) {
22 reachableCount--;
23 }
24 if (s[j] == '0' && reachableCount > 0) {
25 dp[j] = true;
26 }
27 }
28
29 return dp[n - 1];
30 }
31};
32
33int main() {
34 Solution sol;
35 cout << (sol.canReach("011010", 2, 3) ? "true" : "false") << endl;
36 return 0;
37}

Time & Space Complexity

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

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive BranchingO(2^n)O(n)Exhaustive branching over forward jump intervals.Subproblem overlap
2.Naive 1D DPO(n * (maxJump - minJump))O(n)Scan range [j - maxJump, j - minJump] per index.Linear range scan
3.Sliding Window Reachability CountOptimalO(n)O(n)Maintain sliding window counter of reachable predecessor indices.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Failing to check if s[n - 1] == 0 at the start.

Pitfall 2:

Off-by-one errors when subtracting the departing element (must be j - maxJump - 1).

Crucial Edge Cases to Validate:

  • Last element s[n - 1] == 1: Impossible to land; return false immediately.
  • minJump >= n: Can never take a jump; return false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight how sliding window technique seamlessly accelerates range DP from O(n2) to O(n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the sliding window counter optimize the range check from O(maxJump - minJump) to O(1)?

Back to DSA Sheet