AlgoMaster Logo

Jump Game VII

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We start at index 0 of a binary string and want to reach the last index. From any position i, we can jump forward to any position j that falls within the range [i + minJump, i + maxJump], but only if s[j] == '0'. Positions with '1' are blocked, they act like walls we cannot land on.

The question is whether there exists a sequence of valid jumps that takes us from index 0 all the way to the last index.

The jump range has both a lower and an upper bound. Unlike simpler jump game problems where you pick any distance up to some maximum, here every jump must cover at least minJump steps and at most maxJump steps. The minimum bound means you cannot take a single step to skip past a wall of '1's, so the spacing of the '0' positions decides whether a path exists.

This is a reachability problem. We need to determine which indices are reachable from index 0 and check whether the last index is among them. The difficulty is doing this efficiently when the string can be up to 100,000 characters long.

Key Constraints:

  • 2 <= s.length <= 10^5 -- With n up to 100,000, an O(n^2) solution performs on the order of 10^10 operations and times out. We need O(n) or O(n log n).
  • 1 <= minJump <= maxJump < s.length -- The jump range can span nearly the whole string, so a single index may have up to n valid successors. Scanning that range for every index is what drives the brute force to O(n^2).
  • s[i] is '0' or '1' -- Binary input, so reachability reduces to checking a single character per position.

Approach 1: Brute Force (BFS without Deduplication)

Intuition

The problem maps directly onto graph traversal. Each index with '0' is a node, and there is a directed edge from index i to index j whenever j falls in the range [i + minJump, i + maxJump] and s[j] == '0'. The question becomes whether a path exists from node 0 to node n-1.

A BFS from index 0 answers reachability in an unweighted graph. For each index we dequeue, we examine every position in its jump range, and if that position is a '0' and has not been visited, we mark it and enqueue it.

The cost lives in the inner loop. For each index we scan up to maxJump - minJump + 1 positions. When minJump is small, maxJump is large, and the string is full of '0's, that is O(n) work per index, giving O(n^2) overall.

Algorithm

  1. Initialize a queue with index 0 and a visited array.
  2. While the queue is not empty:
    • Dequeue index i.
    • For each j from i + minJump to min(i + maxJump, n - 1):
      • If s[j] == '0' and j is not visited, mark it visited and enqueue it.
      • If j == n - 1, return true.
  3. Return false.

Visualization and Code

Loading animation...

The wasted work comes from overlapping scan ranges: consecutive indices in the queue cover almost the same window, so most positions get inspected many times. The next approach removes that overlap by tracking how far the scan has already reached, so each position is examined at most once.

Approach 2: BFS with Farthest Pointer

Intuition

BFS explores positions left to right: every index it enqueues is larger than the one it was discovered from, so the positions ever scanned only move forward. When we process index i, the window we want to explore is [i + minJump, i + maxJump], and the lower part of that window was almost certainly already scanned while processing an earlier index.

We maintain a pointer farthest that records the highest index any previous scan has reached. When processing index i, instead of scanning from i + minJump, we start from max(i + minJump, farthest + 1). Each position in the string then enters a scan at most once, and the total scanning work over the whole BFS is O(n).

Algorithm

  1. If the last character is '1', return false immediately.
  2. Initialize a queue with index 0, a visited array, and farthest = 0.
  3. While the queue is not empty:
    • Dequeue index i.
    • Compute the start of the scan range: start = max(i + minJump, farthest + 1).
    • Compute the end: end = min(i + maxJump, n - 1).
    • For each j from start to end:
      • If s[j] == '0', mark it visited and enqueue it.
    • Update farthest = max(farthest, i + maxJump).
  4. Return visited[n - 1].

Visualization and Code

Loading animation...

The BFS reaches O(n) but still carries a queue and a farthest pointer. The same reachability can be computed as a dynamic programming recurrence: index j is reachable when some index in [j - maxJump, j - minJump] is reachable. A running prefix sum answers that range query in O(1), removing the queue entirely.

Approach 3: DP with Prefix Sum

Intuition

Define dp[j] = true when index j is reachable from index 0. The recurrence is: dp[j] = true if s[j] == '0' and at least one index i in [j - maxJump, j - minJump] has dp[i] == true. That predecessor window is exactly the set of indices that could legally jump forward and land on j.

Checking the recurrence by scanning the whole window for each j is O(n * range) again. A prefix sum collapses the range query to O(1): the count of reachable indices in [j - maxJump, j - minJump] is positive exactly when some predecessor can reach j. Maintaining that count incrementally as j advances gives an O(n) solution with a single pass and no queue.

Algorithm

  1. Create a boolean array dp of size n. Set dp[0] = true.
  2. Maintain a prefix sum variable pre initialized to 0.
  3. For each index j from 1 to n-1:
    • If j >= minJump, add dp[j - minJump] to pre (this index just entered the valid range).
    • If j > maxJump, subtract dp[j - maxJump - 1] from pre (this index just left the valid range).
    • If s[j] == '0' and pre > 0, set dp[j] = true.
  4. Return dp[n - 1].

Visualization and Code

Loading animation...