Jump GameJump game

01Why it exists

Reach for it when you see:Whether the end is reachable, furthest reachable position, fewest jumps, how many steps forward each cell allows, covering a whole span with the fewest pieces, whether a fuel tank ever goes negative.

02The core idea

Jump Game: nums[i] is the furthest number of steps you may jump forward from cell i, and the question is whether you can get from cell 0 to the last cell. The brute-force answer tries every landing spot with DFS or DP, O(n²). The greedy answer keeps just one variable, far, the furthest position you are certain you can stand on. Sweep left to right: if i > far, cell i is out of reach and you return false immediately; otherwise far = max(far, i + nums[i]). Finishing the sweep, or far covering the end, means true. O(n) time and O(1) space.

Why is the furthest position enough? Because the reachable cells are always one unbroken run from 0 to far: if you can jump to far, you can also land on every cell before it, simply by jumping shorter. So "can I reach i" is exactly "is i ≤ far", and there is no need to remember reachability cell by cell. That observation collapses DP's n states into a single number, which is the classic reason a greedy solution can replace a DP one.

Jump Game II asks for the fewest jumps. Think of it as BFS: jump 0 reaches the range [0, nums[0]], jump 1 reaches the furthest point attainable from anywhere in that range, and so on. In code, cur_end holds the right edge of the current level and far the furthest point of the next one; reaching i == cur_end means the level is exhausted, so you spend a jump and set cur_end = far. Taking the furthest-extending landing spot at each level is the greedy choice, and it is safe: no optimal solution can land further than far at this level, so swapping in far never makes things worse. The loop only runs to n − 2, since standing on the last cell requires no further jump.

Common mistakes: DP solves the first problem correctly too, but it costs an extra O(n) of space, and an interviewer generally expects O(1). In the second problem, "jump to the cell with the largest nums value" is wrong — what you compare is i + nums[i] (how far you can get), not nums[i] (how far you can jump). And do not drop the max when updating far: jumping somewhere nearer than the current reach never shrinks the reachable range.

03The algorithm

1. 1far = 0. Sweep rightwards starting at i = 0.
2. 2If i > far, cell i cannot be reached, so return false.
3. 3far = max(far, i + nums[i]). If far >= n − 1, return true.
4. 4For the fewest-jumps version, also track cur_end (the right edge of the current jump) and jumps. When the sweep reaches i == cur_end, do jumps += 1 and cur_end = far.
5. 5The loop only runs to n − 2, stops early once cur_end >= n − 1, and returns jumps.

04Interactive demo

Switch between the two problems and the two arrays. Green cells are the ones currently known to be reachable, and far only ever grows to the right. The fewest-jumps version adds the yellow boundary cur_end, and reaching that boundary costs one jump; the yellow cells mark where each jump starts. Try the array that gets stuck on a 0 and watch how far grinds to a halt.

05Code

Reachability, fewest jumps, and the identically shaped Gas Station problem. All three functions are one sweep plus a variable or two.

# Jump Game (LeetCode 55): can you get from index 0 to the last cell?
def can_jump(nums):
    far = 0                                  # furthest position we are sure we can stand on
    for i, step in enumerate(nums):
        if i > far:                          # this cell is out of reach, so everything after it is too
            return False
        far = max(far, i + step)
        if far >= len(nums) - 1:             # the end is already covered, so stop early
            return True
    return True


# Jump Game II (LeetCode 45): fewest jumps (the problem guarantees the end is reachable)
def min_jumps(nums):
    jumps = 0
    cur_end = 0                              # right edge this jump can reach (one BFS level)
    far = 0                                  # furthest the next jump can reach
    for i in range(len(nums) - 1):           # standing on the last cell needs no further jump
        far = max(far, i + nums[i])
        if i == cur_end:                     # we hit this level's edge, so we have to jump
            jumps += 1
            cur_end = far
            if cur_end >= len(nums) - 1:
                break
    return jumps


# Same shape in different clothes: Gas Station (LeetCode 134)
# Enough fuel overall guarantees a solution; if the tank goes negative on the way from start, no index from start to here can be the starting point
def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start


if __name__ == "__main__":
    print(can_jump([2, 3, 1, 1, 4, 1, 0, 2, 1]))   # True
    print(can_jump([3, 2, 1, 0, 4]))               # False
    print(min_jumps([2, 3, 1, 1, 4, 1, 0, 2, 1]))  # 3
    print(can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))   # 3

06Practice

• LeetCode 55Jump GameMedium
• LeetCode 45Jump Game IIMedium
• LeetCode 134Gas StationMedium
• LeetCode 1024Video Stitching (interval cover; the same as Jump Game II)Medium
• LeetCode 1306Jump Game III (jumps may go left, so use BFS)Medium
• LeetCode 1326Minimum Number of Taps to Open to Water a GardenHard