Jump Game VII - Video Solutions

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.