Jump Game looks like dynamic programming. “Can I reach the end?” invites a dp[i] = can I reach index i?dp[i] = can I reach index i? table, and that works — in $O(n^2)$.

The greedy insight collapses it to $O(n)$ and one variable:

You do not need to know which path reaches an index. You only need to know how far you can reach at all.

Reachability is a single number, not a set. Because it only ever grows, one forward pass maintaining max_reachmax_reach answers the question completely.

What you’ll learn

• The max_reachmax_reach scan, and why “if i > reachi > reach, fail” is a complete test.
• The level-BFS view of minimum jumps — why LC 45 counts jumps without ever choosing one.
• The two-part structure of Gas Station: a feasibility check plus a restart rule.
• Why these greedies are provably optimal, and where the same shape fails.
• Three real LeetCode problems solved in the browser: 55, 45, 134.

The cue

Pattern 1 — can I get there at all?

Sweep left to right maintaining the furthest index reachable so far. If the loop ever arrives at an index beyond that reach, there is a gap nothing can cross.

def can_jump(nums):
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False              # a gap: nothing reaches index i
        reach = max(reach, i + jump)
    return True
 
 
print(can_jump([2, 3, 1, 1, 4]))      # True
print(can_jump([3, 2, 1, 0, 4]))      # False -- stuck at the 0

def can_jump(nums):
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False              # a gap: nothing reaches index i
        reach = max(reach, i + jump)
    return True
 
 
print(can_jump([2, 3, 1, 1, 4]))      # True
print(can_jump([3, 2, 1, 0, 4]))      # False -- stuck at the 0

$O(n)$ time, $O(1)$ space.

Pattern 2 — minimum jumps, as implicit BFS

For the number of jumps, think in levels, exactly like BFS: level 0 is index 0; level 1 is everything reachable in one jump; level 2 everything reachable in two. The answer is the level containing the last index.

You never decide which jump to take. You only notice when the current level is exhausted and a new one must begin.

def min_jumps(nums):
    jumps = 0
    current_end = 0        # right edge of the current BFS level
    farthest = 0           # right edge of the NEXT level
 
    for i in range(len(nums) - 1):        # note: stop BEFORE the last index
        farthest = max(farthest, i + nums[i])
        if i == current_end:              # current level exhausted
            jumps += 1                    # commit to one more jump
            current_end = farthest        # descend into the next level
    return jumps
 
 
print(min_jumps([2, 3, 1, 1, 4]))   # 2  -> 0 -> 1 -> 4

def min_jumps(nums):
    jumps = 0
    current_end = 0        # right edge of the current BFS level
    farthest = 0           # right edge of the NEXT level
 
    for i in range(len(nums) - 1):        # note: stop BEFORE the last index
        farthest = max(farthest, i + nums[i])
        if i == current_end:              # current level exhausted
            jumps += 1                    # commit to one more jump
            current_end = farthest        # descend into the next level
    return jumps
 
 
print(min_jumps([2, 3, 1, 1, 4]))   # 2  -> 0 -> 1 -> 4

Pattern 3 — feasibility plus restart (Gas Station)

Gas Station has two independent halves, and separating them is what makes it easy:

1. Is any circuit possible? Only if sum(gas) >= sum(cost)sum(gas) >= sum(cost). Otherwise return -1-1 immediately — no starting point can work.
2. Given that one exists, which index? Sweep once with a running tank. Whenever the tank goes negative at index ii, no start in [current_start, i][current_start, i] can work, so jump the candidate start to i + 1i + 1 and reset the tank.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1                   # globally impossible
 
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                # cannot get from `start` past i
            start = i + 1           # so try starting after i
            tank = 0
    return start
 
 
print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1                   # globally impossible
 
    start = 0
    tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                # cannot get from `start` past i
            start = i + 1           # so try starting after i
            tank = 0
    return start
 
 
print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3

Complexity

The variant map

Practice — real LeetCode problems

LC 55 — Jump Game · Medium

Problem. You start at index 00 of numsnums, where nums[i]nums[i] is the maximum jump length from index ii. Return TrueTrue if you can reach the last index.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, 0 <= nums[i] <= 10^50 <= nums[i] <= 10^5.

Examples. [2,3,1,1,4][2,3,1,1,4] gives TrueTrue · [3,2,1,0,4][3,2,1,0,4] gives FalseFalse (the 00 at index 3 is a wall) · [0][0] gives TrueTrue (already there)

LC 45 — Jump Game II · Medium

Problem. Same setup, but you are guaranteed to be able to reach the last index. Return the minimum number of jumps required.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, 0 <= nums[i] <= 10000 <= nums[i] <= 1000, and reaching the end is always possible.

Examples. [2,3,1,1,4][2,3,1,1,4] gives 22 (index 0 → 1 → 4) · [2,3,0,1,4][2,3,0,1,4] gives 22 · [0][0] gives 00

LC 134 — Gas Station · Medium

Problem. There are nn gas stations in a circle. gas[i]gas[i] is the fuel available at station ii, and cost[i]cost[i] is the fuel needed to travel from ii to i+1i+1. Starting with an empty tank, return the index of the station from which you can complete the circuit, or -1-1 if none exists. The answer is guaranteed unique.

Constraints. 1 <= len(gas) == len(cost) <= 10^51 <= len(gas) == len(cost) <= 10^5, 0 <= gas[i], cost[i] <= 10^40 <= gas[i], cost[i] <= 10^4.

Examples. gas = [1,2,3,4,5], cost = [3,4,5,1,2]gas = [1,2,3,4,5], cost = [3,4,5,1,2] gives 33 · gas = [2,3,4], cost = [3,4,3]gas = [2,3,4], cost = [3,4,3] gives -1-1

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Single element — [0][0]; LC 55 gives TrueTrue, LC 45 gives 00. The loop-bound test.
• Leading zero with length > 1 — [0, 1][0, 1]; unreachable, FalseFalse.
• A zero you can jump over — [2,0,0][2,0,0] gives TrueTrue; a zero is only fatal if you must land and stop on it.
• Zero that traps you — [3,2,1,0,4][3,2,1,0,4]; the canonical FalseFalse.
• Very large jump values — i + nums[i]i + nums[i] may exceed the last index; harmless with maxmax, but do not index with it.
• All zeros — [0,0,0][0,0,0] is FalseFalse for LC 55 (length > 1).
• Gas equals cost exactly — feasible with zero slack; ([5],[4])([5],[4]) and ([3,1,1],[1,2,2])([3,1,1],[1,2,2]) cover the boundary.
• Single station (LC 134) — valid if gas[0] >= cost[0]gas[0] >= cost[0].
• Tank exactly zero mid-route — 00 is not negative, so the trip continues; only < 0< 0 triggers a restart.

Recap

• Track how far you can reach, not how you got there. Reachability is a contiguous prefix, so one integer replaces an entire DP array — $O(n)$ and $O(1)$.
• Can I reach the end? Fail the moment the scan stands beyond reachreach.
• Minimum jumps is BFS by levels with the queue replaced by current_endcurrent_end and farthestfarthest. Loop to len(nums) - 1len(nums) - 1, or a single element wrongly costs a jump.
• Gas Station splits into a global feasibility check (sum(gas) >= sum(cost)sum(gas) >= sum(cost)) and a local restart rule, which together avoid simulating the wrap-around.
• Covering a range sorts by start and extends furthest; selecting non-overlapping intervals sorts by end. Ask which you are doing.
• The greedy dies when the reachable set stops being contiguous — backward or exact-length jumps mean real BFS.

Next: Sorting with Custom Comparators — the greedy prerequisite, and how to express an ordering that is not just “ascending”.