Jump Game VII solution and explanation
Google
9 more videos on this problem
Jump Game VII - Leetcode 1871 - PythonNeetCode · 12:28 · 23K views
Jump Game VII | Brute Force | Optimal | Simple Intuition | Leetcode 1871 | codestorywithMIKcodestorywithMIK · 36:47 · 7K views
Jump Game VII | Live Coding with Explanation | Leetcode - 1871Algorithms Made Easy · 15:27 · 4K views
Jump Game VII | LeetCode 1871 | Coders CampCoders Camp · 10:03 · 3K views
LeetCode 1871. Jump Game VIIHappy Coding · 15:06 · 942 views
Leetcode 1871 | Jump Game VII | leetcode POTD | Dp | Sliding Window | DSACode With Vick · 22:50 · 701 views
1871. Jump Game VII (Leetcode Medium)Programming Live with Larry · 14:21 · 622 views
Jump Game VII | LeetCode 1871 | Brute Force | Optimization | Dry Run + CodeStreak To Scale · 6:50 · 499 views
Jump Game VII | Leetcode - 1871Shivam Gupta · 20:31 · 463 views
1871. Jump Game VII | Leetcode Daily - PythonLeetcode Daily · 7:33 · 362 views
The problem
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.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.
def canReach(s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
reachable = [False] * n
reachable[0] = True
farthest = 0
for i in range(n):
if reachable[i]:
for j in range(max(i + minJump, farthest + 1), min(i + maxJump + 1, n)):
if s[j] == '0':
reachable[j] = True
farthest = i + maxJump
return reachable[-1]class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
boolean[] reachable = new boolean[n];
reachable[0] = true;
int farthest = 0;
for (int i = 0; i < n; i++) {
if (reachable[i]) {
for (int j = Math.max(i + minJump, farthest + 1); j <= Math.min(i + maxJump, n - 1); j++) {
if (s.charAt(j) == '0') reachable[j] = true;
}
farthest = i + maxJump;
}
}
return reachable[n - 1];
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
vector<bool> reachable(n, false);
reachable[0] = true;
int farthest = 0;
for (int i = 0; i < n; i++) {
if (reachable[i]) {
for (int j = max(i + minJump, farthest + 1); j <= i + maxJump && j < n; j++) {
if (s[j] == '0') reachable[j] = true;
}
farthest = i + maxJump;
}
}
return reachable[n - 1];
}
};var canReach = function(s, minJump, maxJump) {
const n = s.length;
const reachable = Array(n).fill(false);
reachable[0] = true;
let farthest = 0;
for (let i = 0; i < n; i++) {
if (reachable[i]) {
for (let j = Math.max(i + minJump, farthest + 1); j <= Math.min(i + maxJump, n - 1); j++) {
if (s[j] === '0') reachable[j] = true;
}
farthest = i + maxJump;
}
}
return reachable[n - 1];
};#include <stdbool.h>
#include <string.h>
bool canReach(char * s, int minJump, int maxJump) {
int n = strlen(s);
bool *reachable = (bool*)calloc(n, sizeof(bool));
reachable[0] = true;
int farthest = 0;
for (int i = 0; i < n; i++) {
if (reachable[i]) {
for (int j = max(i + minJump, farthest + 1); j <= i + maxJump && j < n; j++) {
if (s[j] == '0') reachable[j] = true;
}
farthest = i + maxJump;
}
}
bool result = reachable[n - 1];
free(reachable);
return result;
}public class Solution {
public bool CanReach(string s, int minJump, int maxJump) {
int n = s.Length;
bool[] reachable = new bool[n];
reachable[0] = true;
int farthest = 0;
for (int i = 0; i < n; i++) {
if (reachable[i]) {
for (int j = Math.Max(i + minJump, farthest + 1); j <= Math.Min(i + maxJump, n - 1); j++) {
if (s[j] == '0') reachable[j] = true;
}
farthest = i + maxJump;
}
}
return reachable[n - 1];
}
}This Python solution makes use of a list to track if each position in the string is reachable. By iterating through the string, it checks each index, marks reachable indices, and determines if the final index can be reached following the same logic as previous implementations.
Time Complexity: O(n)
Space Complexity: O(n)
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.
def canReach(s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
dp = [False] * n
dp[0] = True
reached = 0
for i in range(1, n):
if i >= minJump and dp[i - minJump]:
reached += 1
if i > maxJump and dp[i - maxJump - 1]:
reached -= 1
dp[i] = (s[i] == '0' and reached > 0)
return dp[-1]class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
boolean[] dp = new boolean[n];
dp[0] = true;
int reached = 0;
for (int i = 1; i < n; i++) {
if (i >= minJump && dp[i - minJump]) {
reached++;
}
if (i > maxJump && dp[i - maxJump - 1]) {
reached--;
}
dp[i] = (s.charAt(i) == '0' && reached > 0);
}
return dp[n - 1];
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
vector<bool> dp(n, false);
dp[0] = true;
int reached = 0;
for (int i = 1; i < n; i++) {
if (i >= minJump && dp[i - minJump]) {
++reached;
}
if (i > maxJump && dp[i - maxJump - 1]) {
--reached;
}
dp[i] = (s[i] == '0' && reached > 0);
}
return dp[n - 1];
}
};var canReach = function(s, minJump, maxJump) {
const n = s.length;
const dp = Array(n).fill(false);
dp[0] = true;
let reached = 0;
for (let i = 1; i < n; i++) {
if (i >= minJump && dp[i - minJump]) {
reached++;
}
if (i > maxJump && dp[i - maxJump - 1]) {
reached--;
}
dp[i] = (s[i] === '0' && reached > 0);
}
return dp[n - 1];
};#include <stdbool.h>
#include <string.h>
bool canReach(char * s, int minJump, int maxJump) {
int n = strlen(s);
bool *dp = (bool*)calloc(n, sizeof(bool));
dp[0] = true;
int reached = 0;
for (int i = 1; i < n; i++) {
if (i >= minJump && dp[i - minJump]) {
reached++;
}
if (i > maxJump && dp[i - maxJump - 1]) {
reached--;
}
dp[i] = (s[i] == '0' && reached > 0);
}
bool result = dp[n - 1];
free(dp);
return result;
}public class Solution {
public bool CanReach(string s, int minJump, int maxJump) {
int n = s.Length;
bool[] dp = new bool[n];
dp[0] = true;
int reached = 0;
for (int i = 1; i < n; i++) {
if (i >= minJump && dp[i - minJump]) {
reached++;
}
if (i > maxJump && dp[i - maxJump - 1]) {
reached--;
}
dp[i] = (s[i] == '0' && reached > 0);
}
return dp[n - 1];
}
}Similar to the other solutions, the Python implementation efficiently tracks reachability using a fixed-length window. By focusing on counting reachable indices within the jump window, it skips recalculating the same positions.
Time Complexity: O(n)
Space Complexity: O(n)
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.
function canReach(s: string, minJump: number, maxJump: number): boolean {
const n = s.length;
const pre: number[] = Array(n + 1).fill(0);
pre[1] = 1;
const f: boolean[] = Array(n).fill(false);
f[0] = true;
for (let i = 1; i < n; ++i) {
if (s[i] === '0') {
const [l, r] = [Math.max(0, i - maxJump), i - minJump];
f[i] = l <= r && pre[r + 1] - pre[l] > 0;
}
pre[i + 1] = pre[i] + (f[i] ? 1 : 0);
}
return f[n - 1];
}func canReach(s string, minJump int, maxJump int) bool {
n := len(s)
pre := make([]int, n+1)
pre[1] = 1
f := make([]bool, n)
f[0] = true
for i := 1; i < n; i++ {
if s[i] == '0' {
l, r := max(0, i-maxJump), i-minJump
f[i] = l <= r && pre[r+1]-pre[l] > 0
}
pre[i+1] = pre[i]
if f[i] {
pre[i+1]++
}
}
return f[n-1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n) |
| Sliding Window Optimization | Time Complexity: O(n) |
| Prefix Sum + Dynamic Programming | – |
Complexity analysis
| 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 |
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.