jump-game

Difficulty: Medium  ·  Topic: 1-D Dynamic Programming  ·  Practice it on parikshan: /practice/jump-game/start

The story

A Cloudflare Workers deployment publishes a chain of edge handlers. Each handler exposes a number representing how many downstream handlers it is willing to forward to in a single hop (the rate budget). The platform team wants to know one thing: starting at the first handler, can a request reach the final handler at all? Some handlers have a budget of 0 (a dead-end sink); if all forwarding paths terminate at one of these before hitting the last handler, deployment is broken.

That reachability question is jump-game. The same shape appears in dependency resolution chains (will the build reach the target if every step has bounded look-ahead?), in failover topologies, in courseware progression where each lesson unlocks at most k ahead, and in firmware rollout pipelines on Tesla and Amazon Devices fleets where each gateway forwards updates up to a budget.

This problem also has a beautiful twin in the same statement: the DP solution is correct and educational, but a greedy solution beats it. The lesson is recognising when greedy works.

What's actually being asked

You have an array nums of non-negative integers. You start at index 0. From index i you may jump to any index in [i+1, i+nums[i]]. Return true if you can reach index n-1, otherwise false.

Examples:

• nums = [2, 3, 1, 1, 4] → true. Jump 0 → 1 → 4.
• nums = [3, 2, 1, 0, 4] → false. Every path lands on the 0 at index 3 and stalls.
• nums = [0] → true. Already at the last index, no jumps needed.
• nums = [1, 0, 1, 0] → false. From index 1 you cannot reach index 2.

The naive approach

Recursion on every legal jump:

def can_jump(i, nums):
    if i >= len(nums) - 1: return True
    for k in range(1, nums[i] + 1):
        if can_jump(i + k, nums): return True
    return False

Exponential. For n = 30 this is already huge; for n = 10⁵ it is impossible.

The key insight

The DP framing is correct and educational. Let dp[i] be True if index i is reachable from 0. Then dp[0] = True and dp[i] = True iff some earlier index j < i is True and j + nums[j] >= i.

# DP recurrence:
# dp[i] = OR over j in [0..i-1] of ( dp[j] AND j + nums[j] >= i )
# dp[0] = True
# Answer = dp[n-1]

That works. It is O(n²): for each i, scan backwards over potential predecessors. Acceptable up to n ~ 5000. Past that, you need something better.

The key insight: then the greedy

The DP is wasteful because reachability is monotone: if any index j <= i was reachable, then every index in [0, j + nums[j]] is also reachable. So instead of recording a True/False per index, just track one number: the furthest index reachable so far, call it reach.

# Greedy / collapsed DP:
# reach = 0
# For i from 0 to n-1:
#   if i > reach: return False   (no predecessor lands here)
#   reach = max(reach, i + nums[i])
#   if reach >= n - 1: return True
# return True

This is O(n), O(1) space. Why does greedy succeed here when greedy fails on coin-change? Because the local choice cannot make a future state unreachable. If you can reach i at all, you can reach i+1, i+2, ..., up to i + nums[i]. There is no scenario where jumping "longer" forecloses a future jump, because shorter jumps are always available from the same launchpad. The reachable region is a contiguous prefix, summarised by its right edge.

The four DP questions, in greedy collapsed form:

1. State: reach, a single integer: the furthest index reachable using any prefix of decisions.
2. Base case: reach = 0 at the start (you are at index 0, so 0 is reachable).
3. Transition: reach = max(reach, i + nums[i]) for each i you can reach. If at any point i > reach, you cannot get to i, so you cannot get further.
4. Answer: reach >= n - 1 once the loop ends, or True the moment reach >= n - 1 mid-scan.

Step-by-step approach

The pure greedy (recommended in production):

def can_jump(nums):
    n = len(nums)
    reach = 0
    for i in range(n):
        if i > reach:
            return False
        if i + nums[i] > reach:
            reach = i + nums[i]
        if reach >= n - 1:
            return True
    return True

The DP form (educational, O(n²)):

def can_jump_dp(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True
    for i in range(1, n):
        for j in range(i):
            if dp[j] and j + nums[j] >= i:
                dp[i] = True
                break
    return dp[n-1]

Both return the right answer; only the greedy is fast enough at n = 10⁵.

Worked example

nums = [2, 3, 1, 1, 4], n = 5

Return true on i=1. Verified.

nums = [3, 2, 1, 0, 4], n = 5

Return false at i=4. Verified.

Complexity

• DP form: O(n²) time, O(n) space.
• Greedy form: O(n) time, O(1) space.

The greedy is the only acceptable production answer at n = 10⁵.

Common pitfalls

• Greedy without monotonicity check: writing the greedy without "if i > reach return False" silently scans past unreachable indices and updates reach from invalid launchpads. Wrong answer.
• Stopping at reach == n - 1 instead of reach >= n - 1: an over-shoot is still valid; you do not need to land on n-1 precisely.
• Using >= nums[i] instead of <= nums[i]: a classic confusion. nums[i] is the maximum jump, not the exact jump.
• Treating nums[i] = 0 as a fatal error: it is not. A zero at index i only blocks if no earlier launchpad could overshoot to i + 1. The recurrence catches this; do not write special cases.

Where this shows up in the enterprise

• Cloudflare Workers chains: can a request reach the final handler given per-handler forwarding budgets?
• PagerDuty alert escalation: each level can forward up to k levels above; can the page reach the executive on-call?
• Apple Maps tile fetching: each tile lists how many downstream tiles to prefetch; will the prefetch chain cover the route?
• Amazon Devices firmware staging: each gateway can forward updates up to a per-gateway budget; can the firmware reach every leaf device?
• Google Search index propagation: shards forward to followers with bounded fanout; can the latest snapshot reach every replica?
• NLP tokenisation candidate paths (HuggingFace BPE merge dynamics): given per-position merge ranges, is the full token covered?
• Genomics scaffolding (Illumina assemblies): contigs anchor to others within a max overlap window; is the genome covered end-to-end?

The pattern is universal: "given per-step bounded look-ahead, is the end reachable?" Greedy with a single reach variable answers it in linear time.

Variants you'll see elsewhere

• jump-game-ii: not "can you reach", but "minimum number of jumps to reach the end". Greedy still, but you track BFS levels. The next article in this cluster.
• jump-game-iii: from each index you may jump exactly nums[i] left or right; reach any index with value 0. BFS / DFS over a graph.
• jump-game-iv: jump left, right, or to any index with the same value; BFS with adjacency by value.
• jump-game-v: jumps constrained by intermediate-element values; usually DP with memoisation.
• frog-jump: each jump depends on the previous jump size; DP with (position, last_jump_size) state.

The jump-game family is a fantastic survey of "what is the right algorithmic family for this twist": linear greedy, BFS, DP, or graph search.

How parikshan turns this into a learning loop

This problem is the textbook "DP is correct but greedy is better" lesson.

1. Read this article and write the DP recurrence first. Then realise the DP collapses to a single number because reachability is monotone. That progression is the entire pedagogical payoff.
2. Practice mode with no AI: code the DP, time it on n = 1000, watch it pass. Time it on n = 10⁵; watch it TLE. Now code the greedy and watch it pass instantly.
3. AI training: Optimise. Submit the O(n²) DP and ask the assistant to optimise. The good response is the greedy collapse; the mediocre response is "use early termination" without the collapse.
4. AI training: Explain. Ask "why does greedy work here but not on coin-change?". The answer (local choice does not foreclose future reachability) is the entire skill of recognising the greedy family.
5. Exam mode: redo cold. The bank's adversarial test on this problem includes [0] (singleton zero), [1, 0, 1, 0] (looks tractable, is not), and [100000, 0, 0, ..., 0] (one big jump). The greedy handles all three; sloppy DP TLEs on the last.

In the AI-integrated workspace

The classic AI failures on this problem:

• The over-engineered DP: an agent asked "is the end reachable" produces a memoised recursion with a visited set. It works but is O(n²); fails the stress test.
• The greedy bug: an agent collapses to reach but forgets the i > reach guard. Sample tests pass; the adversarial [3, 2, 1, 0, 4] returns true (wrong) because the greedy overshoots past the dead 0 without noticing it cannot get to index 3.
• The strict-equality bug: returns false because the loop terminates exactly when reach == n - 1 but the early-return check uses > instead of >=. Off-by-one classic.

The 2027 engineer's discipline:

1. State the question precisely: "can you reach", not "how many jumps", not "shortest path". Different questions, different algorithms.
2. Ask for greedy with a single state variable. "Maintain reach, the furthest index reachable. For each i, if i > reach return False, else update reach."
3. Verify on [3, 2, 1, 0, 4]. The answer must be false. If the agent's code returns true, the greedy guard is wrong; reject the code.
4. Verify on [2, 0]. The answer must be true (jump from 0 to 1, which is the last index). Off-by-one catcher.
5. Do not let the agent escalate to a graph BFS unless the variant truly demands one (which jump-game-iii and beyond do). On the base jump-game, greedy is the right answer.

A candidate who can articulate "this is reach-based greedy because reachability is monotone" in seven seconds is the candidate who can direct an AI agent to produce a correct, linear-time, ten-line solution. That is the skill the parikshan loop is built to train.