Jump Game 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #55: Jump Game — a classic greedy problem! 🦘

💡 Think of it like this: You're standing on stepping stones. Each stone has a number that tells you the MAXIMUM number of stones you can jump forward. Can you reach the last stone?

# Example 1:
nums = [2, 3, 1, 1, 4]
# Start at index 0 (value 2): can jump 1 or 2 steps
# Jump to index 1 (value 3): can jump 1, 2, or 3 steps
# Jump to index 4: REACHED THE END! ✓
# Answer: True

# Example 2:
nums = [3, 2, 1, 0, 4]
# No matter what, you get stuck at index 3 (value 0)
# Answer: False

The Greedy Insight: Keep track of the farthest position you can possibly reach. If at any point your current position is beyond the farthest reachable — you're stuck!

💭 Now it's your turn! Using the approach above, implement your solution in the editor. You've got this! 💪

Step-by-step trace for [2, 3, 1, 1, 4]:

i=0: farthest=max(0, 0+2)=2 → can reach index 2
i=1: 1 ≤ 2 ✓, farthest=max(2, 1+3)=4 → can reach index 4 (the end!)
i=2: 2 ≤ 4 ✓, farthest=max(4, 2+1)=4
i=3: 3 ≤ 4 ✓, farthest=max(4, 3+1)=4
i=4: 4 ≤ 4 ✓ → reached the end! Return True

Why Greedy works here: We don't need to find the exact path — we just need to know IF we can reach the end. By tracking the farthest reachable index, we get O(n) time, O(1) space.

📋 Instructions

Return True if you can reach the last index.

Track max_reach. For each index i, if i > max_reach return False. Update max_reach = max(max_reach, i+nums[i]).

⚠️ Try solving it yourself first — you'll learn more!

def canJump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:     # Can't reach this position!
            return False
        farthest = max(farthest, i + nums[i])  # Update how far we can go
    return True

🧪 Test Cases

Input

canJump([2,3,1,1,4])

Expected

True

Boolean check

Input

canJump([3,2,1,0,4])

Expected

False

Boolean check

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›