DSA problem

Jump Game VII

MediumGreedyPattern: Greedytop600AmazonGoogleMicrosoftBloombergApple

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.

The naive recursive solution explores every reachable index by trying all jumps in [i + minJump, i + maxJump] from each position. This balloons to exponential time because the same index gets visited from many predecessors. Memoizing the recursion brings it down to O(n * (maxJump - minJump)), but for n up to 10^5 even that quadratic-ish blowup is too slow.

The optimal approach reframes the problem as a BFS over reachable zero-positions but observes that the set of indices reachable in one hop from i is the contiguous window [i + minJump, i + maxJump]. As we sweep i left to right, the window slides forward monotonically. So instead of re-scanning the window, we keep a moving "earliest-not-yet-considered" pointer and only mark fresh zero indices inside the window as reachable.

Concretely, walk i from 0 to n - 1; only process i if it is itself reachable. For each reachable i, expand reachability to every j in [max(i + minJump, lastSeen + 1), i + maxJump] whose s[j] == '0'. Track lastSeen so each index is touched at most once across the whole run, giving a clean O(n) time, O(n) space solution. The boolean reach[n - 1] is the answer.

Examples

Constraints

• 2 <= s.length <= 10^5
• s[i] is either '0' or '1'.
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

greedystringsliding-windowbfsdynamic-programming

Browse all DSA problems