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), ands[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 <= 105s[i] is either '0' or '1'.s[0] == '0'1 <= minJump <= maxJump < s.lengthProblem 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.
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.
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.
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.
Time Complexity: O(n)
Space Complexity: O(n)
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.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n) - where n is the length of the string s. Each index is processed once. |
| Sliding Window Optimization | Time Complexity: O(n) |
| Prefix Sum + Dynamic Programming | — |
| Approach | Time | Space | When 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 Programming | O(n) | O(n) | Preferred optimal solution for interviews; avoids repeated range scans using a running window |
Jump Game VII - Leetcode 1871 - Python • NeetCode • 19,911 views views
Watch 8 more video solutions →Practice Jump Game VII with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor