Jump Game

Each index i in an array holds the maximum jump length from that position. Jump Game problems ask whether you can reach the last index, or how to do it in the fewest jumps. This lesson covers Jump Game I (LeetCode 55), Jump Game II (45), greedy vs DP, and solutions in C, Java, and Python with trace tables.

Overview

From index 0, at each step you may jump forward by 1 up to nums[i] positions. You cannot jump backward.

Array:  index:  0   1   2   3   4
        nums:   2   3   1   1   4

From 0: can land on 1 or 2
From 1: can land on 2, 3, or 4
...
Goal: reach index n-1

Jump Game I — Can Reach End?

Problem (LeetCode 55): Return true if you can reach the last index starting at index 0.

Greedy insight: Track the farthest index reachable so far. If current index i exceeds farthest, you're stuck. Update farthest = max(farthest, i + nums[i]).

Complexity: O(n) time, O(1) space — optimal for this problem.

Jump Game I Greedy Code (C, Java, Python)

Python

def can_jump(nums):
    """LeetCode 55 — greedy farthest reach. O(n) time, O(1) space."""
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False  # cannot reach this index
        reach = max(reach, i + jump)
    return True


if __name__ == "__main__":
    tests = [[2, 3, 1, 1, 4], [3, 2, 1, 0, 4], [0], [2, 0]]
    for nums in tests:
        print(f"canJump({nums}) → {can_jump(nums)}")

Java

public class JumpGameI {

    /** Greedy — track farthest reachable index. */
    public static boolean canJump(int[] nums) {
        int reach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;
            reach = Math.max(reach, i + nums[i]);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[]{2, 3, 1, 1, 4})); // true
        System.out.println(canJump(new int[]{3, 2, 1, 0, 4})); // false
        System.out.println(canJump(new int[]{0}));               // true
    }
}

C

#include <stdio.h>

int max2(int a, int b) { return a > b ? a : b; }

int can_jump(int nums[], int n) {
    int reach = 0, i;
    for (i = 0; i < n; i++) {
        if (i > reach) return 0;
        reach = max2(reach, i + nums[i]);
    }
    return 1;
}

int main(void) {
    int a[] = {2, 3, 1, 1, 4};
    int b[] = {3, 2, 1, 0, 4};
    int c[] = {0};
    printf("%d\n", can_jump(a, 5)); /* 1 */
    printf("%d\n", can_jump(b, 5)); /* 0 */
    printf("%d\n", can_jump(c, 1)); /* 1 */
    return 0;
}

Jump Game I — DP Alternative

Boolean DP: dp[i] = can we reach index i? For each reachable i, mark dp[i+1..i+nums[i]] true.

def can_jump_dp(nums):
    """Jump Game I — O(n²) DP (interview draft, then optimize to greedy)."""
    n = len(nums)
    dp = [False] * n
    dp[0] = True
    for i in range(n):
        if not dp[i]:
            continue
        for step in range(1, min(nums[i], n - 1 - i) + 1):
            dp[i + step] = True
    return dp[n - 1]

Jump Game I Output & Trace

Program output

Greedy trace — nums = [2, 3, 1, 1, 4]

Failure trace — nums = [3, 2, 1, 0, 4]

Jump Game II — Minimum Jumps

Problem (LeetCode 45): Return the minimum number of jumps to reach the last index. Guaranteed that you can reach it.

Greedy (level BFS): Treat jumps as layers. Track current level end end and farthest reachable in this level. When i == end, increment jumps and extend end = farthest.

Complexity: O(n) time, O(1) space.

Jump Game II Code (C, Java, Python)

Python

def jump(nums):
    """LeetCode 45 — minimum jumps, greedy level expansion."""
    n = len(nums)
    if n <= 1:
        return 0

    jumps = 0
    end = 0       # end of current jump level
    farthest = 0  # farthest reachable in current level

    for i in range(n - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:
            jumps += 1
            end = farthest

    return jumps


if __name__ == "__main__":
    tests = [[2, 3, 1, 1, 4], [2, 3, 0, 1, 4], [1, 1, 1, 1]]
    for nums in tests:
        print(f"jump({nums}) → {jump(nums)}")

Java

public class JumpGameII {

    public static int jump(int[] nums) {
        int n = nums.length;
        if (n <= 1) return 0;

        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) {
                jumps++;
                end = farthest;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        System.out.println(jump(new int[]{2, 3, 1, 1, 4})); // 2
        System.out.println(jump(new int[]{2, 3, 0, 1, 4})); // 2
        System.out.println(jump(new int[]{1, 1, 1, 1}));     // 3
    }
}

C

#include <stdio.h>

int jump(int nums[], int n) {
    int jumps = 0, end = 0, farthest = 0, i;

    if (n <= 1) return 0;

    for (i = 0; i < n - 1; i++) {
        if (i + nums[i] > farthest) farthest = i + nums[i];
        if (i == end) {
            jumps++;
            end = farthest;
        }
    }
    return jumps;
}

int main(void) {
    int a[] = {2, 3, 1, 1, 4};
    int b[] = {2, 3, 0, 1, 4};
    int c[] = {1, 1, 1, 1};
    printf("%d\n", jump(a, 5)); /* 2 */
    printf("%d\n", jump(b, 5)); /* 2 */
    printf("%d\n", jump(c, 4)); /* 3 */
    return 0;
}

Jump Game II Output & Trace

Program output

Level trace — nums = [2, 3, 1, 1, 4]

Related Jump Problems

Greedy vs DP

More Examples

Example 1: Single element

Example 2: Zero trap at start (if allowed)

Example 3: Complexity summary

Approach Comparison

Real-Life Applications

Interview Tips

1. Clarify: can reach end (55) vs minimum jumps (45)? Is reaching last index guaranteed?
2. For I: explain greedy farthest — if i > reach, return false early.
3. For II: loop only to n−2; increment jumps when i == end.
4. Offer O(n²) DP first if stuck, then optimize to greedy.
5. Trace [2,3,1,1,4] on whiteboard for both I and II.
6. Counterexample for naive greedy min-jump: always jump max distance is not optimal for min count — level greedy fixes this.
7. Connect to BFS on implicit graph (indices as nodes).
8. Link to word break (reachability) and grid path (forward-only movement).