Command Palette

Search for a command to run...

Hectal
Problem 33.2 · Greedy AlgorithmsMedium

Jump Game

PatternGreedy Choice1D Dynamic Programming

What it teaches: Track the farthest reachable index in one pass.

Practise it on judges as “Jump Game”.

The problem

nums[i] is the maximum jump length from index i. Starting at index 0, return true if you can reach the last index.

Example 1

Input: nums = [2, 3, 1, 1, 4]
Output: true

Example 2

Input: nums = [3, 2, 1, 0, 4]
Output: false

Constraints

  • 1 ≤ n ≤ 10⁴

Pattern clues in the wording

  • → Reachability along a line with variable jumps

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public boolean canJump(int[] nums) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [2,3,1,1,4]
true
2
nums = [3,2,1,0,4]
false
3
nums = [0]
true

From slow to fast

Approaches

1. Farthest reach · O(n)
1

Farthest reach

Time O(n) Space O(1)

If i > reach, return false; otherwise extend reach. Reaching n − 1 means true.

Approach 1
class Solution {
    public 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;
    }
}

Verdict: A DP would be O(n²) for the same answer.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single element (true)
  • A zero you can jump over

Mistakes people make

  • Always taking the biggest jump from the current index.

Interview

Follow-up questions

What if you can jump in both directions (Jump Game III)?