Skip to main content
Talentd

Jump Game VII - Solution & Explanation

MediumStringDynamic ProgrammingSliding WindowPrefix Sum19 min readAsked at: Amazon, Meta, Google +1
Practice this problem

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.

 

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 <= 105
  • s[i] is either '0' or '1'.
  • s[0] == '0'
  • 1 <= minJump <= maxJump < s.length

Approach Overview

Problem Overview: You get a binary string s where 0 means you can land on that index and 1 blocks it. Starting at index 0, you can jump to any index j such that minJump ≤ j - i ≤ maxJump. The goal is to determine whether the last index is reachable.

Approach 1: Breadth-First Search (BFS) (Time: O(n), Space: O(n))

Treat each index as a node in a graph and each valid jump as an edge. Use a queue to run BFS starting from index 0. For each popped index i, iterate through the range [i + minJump, i + maxJump] and push positions where s[j] == '0'. To avoid scanning the same region repeatedly, track the farthest index already explored and only process new indices beyond that boundary. A visited array prevents revisiting nodes. This approach works well because BFS guarantees that every reachable index is processed exactly once.

The idea fits naturally with graph traversal and highlights reachability. The string is essentially a linear graph where edges represent valid jump distances. BFS makes the logic straightforward, though you still need the optimization that avoids repeatedly scanning the same jump window.

Approach 2: Sliding Window Optimization (Time: O(n), Space: O(n))

The optimized approach uses dynamic programming with a sliding window. Define dp[i] as whether index i is reachable. For each position i, check if there exists a reachable index within the window [i - maxJump, i - minJump]. Instead of scanning the entire range each time, maintain a running count of reachable positions inside that window.

As you iterate through the string, expand the window by adding dp[i - minJump] and shrink it by removing dp[i - maxJump - 1]. If the window count is greater than zero and s[i] == '0', mark dp[i] = true. This guarantees each index is processed once, giving linear time complexity.

This sliding window trick avoids repeated range checks and effectively simulates a prefix-sum style reachability check. It turns a potentially quadratic search into a strict O(n) scan.

Recommended for interviews: Interviewers typically expect the sliding window dynamic programming solution. Starting with the BFS interpretation shows you understand the reachability model. Moving to the optimized sliding window approach demonstrates algorithmic maturity by reducing repeated work and achieving true O(n) performance.

Approach 1: Breadth-First Search (BFS) Approach

A BFS approach involves using a queue to explore all possible indices starting from index 0. Each index is checked for the conditions, and if any index meets the criteria, it is added to the queue for further exploration. This ensures all reachable indices are visited.

This solution uses a boolean array to keep track of reachable indices. Starting from index 0, it explores indices within the allowed jump range. If an index is reachable, it is marked in the boolean array. This array is then used to explore further indices until all reachable indices are processed. The result is determined by whether the last index can be reached.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - where n is the length of the string s. Each index is processed once.
Space Complexity: O(n) - for the boolean array to track reachable indices.

Try this approach in the editor →

Approach 2: Sliding Window Optimization

To further optimize, a sliding window or prefix sum method is used to reduce the number of operations needed by focusing on maintaining a window of reachable indices, eliminating inner loops for checking reachable segments, and accumulating results incrementally.

This C solution utilizes a sliding window or prefix sum approach to maintain a count of reachable indices. By checking indices directly within the window constraint, it adds or deducts from the `reached` count, optimizing previous brute-force reach checks per index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Prefix Sum + Dynamic Programming

We define a prefix sum array pre of length n+1, where pre[i] represents the number of reachable positions in the first i positions of s. We define a boolean array f of length n, where f[i] indicates whether s[i] is reachable. Initially, pre[1] = 1 and f[0] = true.

Consider i \in [1, n), if s[i] = 0, then we need to determine whether there exists a position j in the first i positions of s, such that j is reachable and the distance from j to i is within [minJump, maxJump]. If such a position j exists, then we have f[i] = true, otherwise f[i] = false. When determining whether j exists, we can use the prefix sum array pre to determine whether such a position j exists in O(1) time.

The final answer is f[n-1].

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) Approach

Time Complexity: O(n) - where n is the length of the string s. Each index is processed once.
Space Complexity: O(n) - for the boolean array to track reachable indices.

Sliding Window Optimization

Time Complexity: O(n)
Space Complexity: O(n)

Prefix Sum + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS)O(n)O(n)When modeling the problem as graph reachability or when explaining the intuition step-by-step
Sliding Window Dynamic ProgrammingO(n)O(n)Preferred optimal solution for interviews; avoids repeated range scans using a running window

Video Solution

Jump Game VII - Leetcode 1871 - Python • NeetCode • 23,281 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Jump Game VII easy or hard?
Jump Game VII is rated Medium but often feels closer to hard for many candidates. The challenge is recognizing that naive range checks are too slow and applying a sliding window optimization to reduce the complexity to O(n).
How to solve Jump Game VII in O(n)?
Use a DP array where dp[i] indicates if index i is reachable. Maintain a sliding window count of reachable indices between i - maxJump and i - minJump. If the count is positive and s[i] equals '0', mark dp[i] as reachable. Updating the window incrementally keeps the entire algorithm linear.
What is the best approach for Jump Game VII?
The most efficient approach uses sliding window dynamic programming. Track whether each index is reachable and maintain a running count of reachable indices within the window [i - maxJump, i - minJump]. This avoids scanning the entire range for every position and achieves O(n) time complexity.
Is Jump Game VII asked at Google/Amazon/Meta?
Jump Game style problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants test reachability, dynamic programming, and sliding window optimization. Interviewers often expect candidates to move from a BFS idea to an O(n) optimized solution.
What data structure is used in Jump Game VII?
Common implementations use a queue for the BFS approach and an array for dynamic programming. The optimized solution also uses a sliding window counter, similar to prefix sum techniques, to track reachable positions efficiently.
What is the time complexity of Jump Game VII?
The optimal solution runs in O(n) time where n is the length of the string. Each index is processed once while maintaining a sliding window of reachable positions. Space complexity is O(n) for the DP or visited array.
Jump Game VII Python or Java solution approach?
Both Python and Java implementations typically follow the sliding window DP method. Maintain a dp array and update a running window count as you iterate through the string. This keeps the complexity O(n) and works efficiently even for large input sizes.

Ready to solve this problem?

Practice Jump Game VII with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Vowel Strings in Ranges

Next

Jump Game