#55MediumGreedy

Jump Game

Track the maximum reachable index as you move forward.

AmazonMicrosoftAdobeBloomberg

Problem Statement

You are given an integer array nums where nums[i] is the maximum jump length from index i. Return true if you can reach the last index, or false otherwise.

Examples

Example 1

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

Explanation: Jump 1→3→4 or 2→4.

Example 2

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

Explanation: You'll always land on index 3 which has a jump of 0.

Constraints

  • 1 ≤ nums.length ≤ 10⁴
  • 0 ≤ nums[i] ≤ 10⁵

Solutions

1
DP (Boolean array)
TimeO(n²)SpaceO(n)

dp[i] = can we reach index i? For each reachable index, mark all indices reachable from it. O(n²).

Visual Animation
def canJump(nums: list[int]) -> bool:
    n = len(nums)
    dp = [False] * n
    dp[0] = True
    for i in range(n):
        if dp[i]:
            for j in range(1, nums[i]+1):
                if i+j < n: dp[i+j] = True
    return dp[n-1]

Related Concepts

Deepen your understanding with these related topics from our AI Glossary:

Machine LearningBrowse all 190+ concepts →
Deepen your understanding

Want to master the core concepts?

Our free AI Glossary covers 190+ topics — from Greedy to Dynamic Programming, Machine Learning, SQL, and more. Structured learning tracks for every level.

Browse AI Glossary All Problems
39+
AI Models
₹69
Per day used
4
Languages

Stuck? Ask AI to explain it step by step.

Ask Claude, GPT-4o, or Gemini to debug your code, generate test cases, or walk through the intuition. 39+ models. Pay only on days you use it — no subscription required.

Free to start · No credit card required to explore

Get Started Free
Back to all problems