Jump Game VII: BFS with a Sliding Window

LeetCode 1871 is the seventh entry in the Jump Game family, and it brings a twist: instead of an integer array, you are given a binary string. The positions you can land on are constrained by the characters in the string, not by values at each index. The naive DP approach looks clean but will TLE on large inputs. The efficient solution uses BFS with a pointer that prevents redundant scanning, bringing the time down to O(n).

The problem

You are given a binary string s and two integers minJump and maxJump. Starting at index 0 (which is always '0'), you can jump from index i to index j if all of the following are true:

• i + minJump <= j <= i + maxJump
• s[j] == '0'

Return true if you can reach index n - 1, or false otherwise.

Example: s = "011010", minJump = 2, maxJump = 3

From index 0, the jump range is indices 2 through 3. Index 2 has s[2] = '1' (blocked), but index 3 has s[3] = '0' (landable). From index 3, the range is indices 5 through 5 (clamped to the string length). Index 5 has s[5] = '0', so we land there. That is the last index, so the answer is true.

The brute force approach

The most natural way to think about this is dynamic programming. Define dp[i] as whether index i is reachable. For each index i where dp[i] is true, mark all valid targets in [i + minJump, i + maxJump] as reachable.

def can_reach(s, min_jump, max_jump):
    n = len(s)
    dp = [False] * n
    dp[0] = True

    for i in range(n):
        if not dp[i]:
            continue
        for j in range(i + min_jump, min(i + max_jump + 1, n)):
            if s[j] == "0":
                dp[j] = True

    return dp[n - 1]

This works correctly, but the inner loop can scan up to maxJump - minJump + 1 positions for every reachable index. In the worst case (long string of all zeros with large jump range), this is O(n^2) time. That will TLE on inputs with n up to 10^5.

The key insight: sliding window reachability

The brute force wastes time by rescanning the same indices. When index i marks indices in [i + minJump, i + maxJump] as reachable, and then index i + 1 marks indices in [i + 1 + minJump, i + 1 + maxJump], those two windows overlap heavily. Most of the work is redundant.

The fix is to track how far you have already scanned. If you maintain a pointer farthest that records the rightmost index you have already checked, each new BFS node only needs to scan from farthest + 1 to the end of its window. Every index gets scanned at most once across the entire algorithm.

Optimizing with BFS and a pointer

Instead of DP, use a queue-based BFS. Start with index 0 in the queue. For each dequeued index i, the candidate landing zone is [i + minJump, i + maxJump]. But instead of scanning that full range, start scanning from max(i + minJump, farthest + 1). For each j in that range where s[j] == '0', enqueue j. After processing the range, update farthest to i + maxJump.

This guarantees that every index is visited at most once during scanning, because the farthest pointer only moves forward.

Visual walkthrough

Notice how the farthest pointer prevents any index from being scanned more than once. In step 2, we scan indices 2 and 3. In step 3, we scan index 5 (starting from farthest + 1 = 4, but 3 + minJump = 5). The total number of indices scanned across all steps is exactly n.

The code

from collections import deque

def can_reach(s, min_jump, max_jump):
    n = len(s)
    if s[n - 1] == "1":
        return False

    queue = deque([0])
    farthest = 0

    while queue:
        i = queue.popleft()
        start = max(i + min_jump, farthest + 1)
        end = min(i + max_jump, n - 1)

        for j in range(start, end + 1):
            if s[j] == "0":
                if j == n - 1:
                    return True
                queue.append(j)

        farthest = max(farthest, end)

    return False

A few things to note about this implementation:

1. Early exit on the last character: If s[n - 1] == '1', the goal is blocked and we can return false immediately.
2. The farthest pointer: start = max(i + minJump, farthest + 1) ensures we never re-examine an index. This single line is what makes the algorithm O(n).
3. Early return inside the loop: As soon as we find that j == n - 1 is reachable, we return true without processing the rest of the queue.
4. Updating farthest: After scanning the range for the current node, update farthest to max(farthest, end). This captures the fact that everything up to end has been checked.

Complexity analysis

Time: O(n). Each index in the string is scanned at most once thanks to the farthest pointer. Enqueue and dequeue operations are O(1) each. The total work across all iterations of the outer while-loop is bounded by n.

Space: O(n). The queue can hold up to O(n) indices in the worst case (a string of all zeros).

Edge cases to watch for

• Last character is '1': The goal index is blocked. Return false immediately, no BFS needed.
• Single character s = "0": You are already at the last index. Return true.
• No reachable zeros in the first window: If every index in [minJump, maxJump] has s[j] == '1', the queue empties after dequeuing index 0. Return false.
• Very large jump range with sparse zeros: The farthest pointer ensures you still process each index only once, even when maxJump is close to n.

The building blocks

This problem combines two reusable patterns:

1. BFS on implicit graphs

The string indices form the nodes and the jump rules define the edges. BFS explores reachable nodes level by level. You do not need to build an adjacency list. The edges are defined implicitly by the jump range, and you generate neighbors on the fly.

This pattern appears whenever the graph structure is defined by a rule rather than stored explicitly: word ladders, grid traversals, and state-space searches all use the same BFS template.

2. Sliding window pointer for deduplication

The farthest pointer prevents rescanning indices that have already been processed. This is a variant of the sliding window technique. Instead of maintaining a window of active elements, you maintain a frontier that only advances. Any time you have a BFS or DP where neighbor ranges overlap between consecutive nodes, a pointer like this can collapse the quadratic scanning into linear.

The same idea appears in Jump Game II (tracking the farthest reach in each BFS level) and in interval merging problems where you sweep left to right and skip over already-covered territory.

From understanding to recall

You have seen how a single pointer turns an O(n^2) BFS into an O(n) one. The core idea is simple: track how far right you have already scanned, and never go backward. But the implementation details matter. Where exactly do you compute start? When do you update farthest? What about the early exit?

These are the kinds of details that slip away under interview pressure if you have not practiced writing them from memory. Spaced repetition closes that gap. You practice the BFS-with-pointer pattern from scratch at increasing intervals until the code flows automatically.

The BFS-on-implicit-graphs and sliding-window-pointer patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Jump Game - The original reachability problem solved with a greedy scan
• Jump Game II - Minimum number of jumps using BFS-style greedy boundaries
• Sliding Window Pattern - The general technique behind the pointer optimization

CodeBricks breaks Jump Game VII into its BFS-on-implicit-graphs and sliding-window-pointer building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constrained reachability problem shows up in your interview, you do not hesitate. You just write it.