Jump Game

Master this topic with zero to advance depth.

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Visual Representation

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

Index: 0  1  2  3  4
Value: 2  3  1  1  4

- From 0 (2): Can jump to 1 or 2.
- From 1 (3): Can jump to 2, 3, or 4 (Goal!).
Result: True

Medium

Examples

Input: nums = [2, 3, 1, 1, 4]
Output: true
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3, 2, 1, 0, 4]
Output: false
You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Approach 1

Level I: Dynamic Programming (Bottom-Up)

Intuition

We can store whether each index is 'reachable' in a DP table. An index i is reachable if there exists some j < i such that j is reachable AND j + nums[j] >= i.

Thought Process

canReach[i] = true if index i is reachable.
canReach[0] = true.
For each i, check all j < i to see if a jump can land on i.

Pattern Identification

This is Linear DP. While effective, it leads to O(N^2) time.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

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

i	nums[i]	j loop	canReach table	Status
0	2	-	[T, F, F, F, F]	Start
1	3	j=0 (0+2 >= 1)	[T, T, F, F, F]	OK
2	1	j=0 (0+2 >= 2)	[T, T, T, F, F]	OK
4	4	j=1 (1+3 >= 4)	[T, T, T, T, T]	REACHED

java

public class Main {
    public static boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[nums.length - 1];
    }

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

Approach 2

Level II: Top-Down DP (Memoization)

Intuition

The standard DP approach checks all j < i. We can speed it up by also keeping a track of the farthest reachable index instead of building the full table — but for memoization we cache 'can we reach this index from the start?'.

Visual

nums = [2, 3, 1, 1, 4]
memo[0] = True, memo[1] = ?, memo[2] = ?
- Check: can we reach index 1? From 0, jump 1 or 2. Yes!
- Can we reach index 4? From 1, jump 3. Yes! memo[4] = True.

⏱ O(N^2)💾 O(N)

Detailed Dry Run

nums = [2, 3, 1, 1, 4]. memo[1] = True (from 0). memo[4] = True (from 1). Early exit!

java

import java.util.*;

public class Main {
    static Boolean[] memo;
    static int[] nums;
    public static boolean canReach(int i) {
        if (i == 0) return true;
        if (memo[i] != null) return memo[i];
        for (int j = 0; j < i; j++) {
            if (canReach(j) && j + nums[j] >= i) {
                return memo[i] = true;
            }
        }
        return memo[i] = false;
    }

    public static boolean canJump(int[] input) {
        nums = input;
        memo = new Boolean[nums.length];
        return canReach(nums.length - 1);
    }

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

⚠️ Common Pitfalls & Tips

The memoized top-down approach is still O(N^2) in the worst case. The Greedy approach is O(N) and should be preferred for large inputs.

Approach 3

Level III: Optimal (Greedy)

Intuition

We don't need to know all ways to reach an index, just the farthest index we can reach. If we can reach index i, we can also reach everything before it.

Logic Steps

Initialize goal = nums.length - 1.
Iterate through the array from right to left.
If i + nums[i] >= goal, then index i can reach the goal. Update the goal = i.
If at the end goal == 0, return true.

⏱ O(N)💾 O(1)

Detailed Dry Run

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

i	nums[i]	i + nums[i]	Goal	Update?
4	4	8	4	Init
3	1	4	4	3+1 >= 4 (YES), Goal=3
2	1	3	3	2+1 >= 3 (YES), Goal=2
1	3	4	2	1+3 >= 2 (YES), Goal=1
0	2	2	1	0+2 >= 1 (YES), Goal=0

java

public class Main {
    public static boolean canJump(int[] nums) {
        int goal = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }
        return goal == 0;
    }

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

⚠️ Common Pitfalls & Tips

While this problem has a Greedy solution, many similar problems (like Jump Game II) are better solved with DP or BFS. Always check if a greedy choice leads to the global optimum.

← Previous QuestionHouse Robber II

Next Question →Longest Common Subsequence

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.