LeetEye LeetEye
Medium Greedy ~5 min

Jump Game

greedy jump-game

Problem

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.

Examples

Example 1
Input: nums = [2,3,1,1,4]
Output: true
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2
Input: nums = [3,2,1,0,4]
Output: false
You will always arrive at index 3 whose value is 0.
Key Insight

Track the farthest index you can reach. If you ever land on a position beyond your reach, return false.

Track farthest reachable index. At each i, update farthest = max(farthest, i + nums[i]). If i > farthest, stuck.

How to Approach This Problem

Pattern Recognition: When you see keywords like jump game greedy, think Greedy.

Step-by-Step Reasoning

1 At position i, you can jump to:
Answer: Any position from i+1 to i + nums[i]
nums[i] is MAXIMUM jump. You can jump 1, 2, ..., up to nums[i] steps.
2 We greedily track:
Answer: Farthest reachable index
If farthest_reachable >= last_index, we can reach the end.
3 At position i, update farthest to:
Answer: max(farthest, i + nums[i])
Farthest is the max of previous farthest and what we can reach from i.
4 We can't reach the end if:
Answer: i > farthest (we can't reach position i)
If current position i is beyond farthest reachable, we're stuck.
5 We can return True early when:
Answer: farthest >= last_index
If we can already reach or exceed the last index, we're done.

Solution

def canJump(nums: List[int]) -> bool:
    farthest = 0
    
    for i in range(len(nums)):
        # Can't reach position i
        if i > farthest:
            return False
        
        farthest = max(farthest, i + nums[i])
        
        # Can reach the end
        if farthest >= len(nums) - 1:
            return True
    
    return True

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye