MediumArrayDynamic ProgrammingGreedyUpdated Sep 2026

55. Jump Game

Asked at Oracle, Bloomberg

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

2

Problem

You get an array of non-negative integers called nums. You start standing on index 0. The value at each index tells you the maximum number of steps you may jump forward from that position. You can jump any distance from 1 up to that value, and you may not jump backward.

Return true if some sequence of jumps lets you land on the last index of the array. Otherwise return false.

A value of 0 means you are stuck at that index — you can only jump 0 steps, so you cannot move forward from there.

How far can you jump from each index

nums2311401234Start at index 0 (green) and try to land on index 4(orange), the last indexnums2311401234In [3,2,1,0,4] index 3 holds 0 — landing there endsyour run
Each number is the maximum jump length from that position, and you always move to the right.

Constraints

  • ●1 <= nums.length <= 10^4
  • ●0 <= nums[i] <= 10^5

Examples

Example 1
Inputnums = [2,3,1,1,4]
Outputtrue
WhyFrom index 0 you may jump 1 or 2 steps. Jump 1 step to index 1. From index 1 you may jump up to 3 steps, and 3 steps lands exactly on index 4, the last index.
Example 2
Inputnums = [3,2,1,0,4]
Outputfalse
WhyIndex 3 holds 0, so once you land there you cannot move. From index 0 you can jump 1, 2 or 3 steps, and every one of those paths eventually forces you onto index 3. The last index 4 stays out of reach.

Asked At

2 companies
CompanyDifficulty
OracleMediumView all Oracle questions →
BloombergMediumView all Bloomberg questions →

How to Think About It

1

Think about what each index value means — it tells you how far you can jump from that position.

2

A brute force approach tries every possible jump from each index using recursion, leading to exponential time.

3

Dynamic programming can optimize by storing whether each index is reachable, but this still requires O(n) space.

4

A greedy approach tracks the farthest reachable index as you iterate through the array.

5

If at any point the current index exceeds the farthest reachable index, return false. Otherwise, return true.

Optimal Approach

Iterate through the array while maintaining the farthest index you can reach. For each position i, update the farthest reachable index as max(farthest, i + nums[i]). If at any point the current index i is beyond the farthest reachable index, you cannot proceed and return false. If you complete the loop, the last index is reachable. This greedy approach runs in O(n) time and O(1) space.

Track the farthest reachable index

numsreach = 22311401234ii = 0: from here you can reach index 2, so farthest =max(0, 0+2) = 2numsreach = 42311401234ii = 1: i is inside the reach, and 1+3 = 4 pushesfarthest all the way to the last indexnums2311401234ii = 4 is still within reach, so the loop finishes andwe return trueif i > farthest: return Falsefarthest = max(farthest, i + nums[i])
Walk left to right. If the current index is past the farthest you can reach, the answer is false.
ComplexityTime O(n)Space O(1)One left-to-right pass, and only a single variable (the farthest reachable index) is stored.

What Trips People Up in Real Interviews

1

Clarify whether you can jump exactly or at most the given number of positions.

2

Start with the brute force recursion to show problem understanding before optimizing.

3

Explain the greedy insight clearly — you only need to track the maximum reachable index.

4

Mention that this can also be solved with DP but greedy is optimal at O(n) time and O(1) space.

5

Edge cases: single element array (always true), first element is 0 and array has more than one element (false).

Solution Code

O(n) time
def canJump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Jump Game problem?

You are given an integer array nums where each element represents the maximum number of positions you can jump forward from that index. Determine whether you can reach the last index starting from the first index.

How do you solve Jump Game?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Jump Game?

Jump Game is asked at Oracle, Bloomberg. It is a medium difficulty problem.

What are common mistakes on Jump Game?
  • Clarify whether you can jump exactly or at most the given number of positions.
  • Start with the brute force recursion to show problem understanding before optimizing.
  • Explain the greedy insight clearly — you only need to track the maximum reachable index.
  • Mention that this can also be solved with DP but greedy is optimal at O(n) time and O(1) space.
  • Edge cases: single element array (always true), first element is 0 and array has more than one element (false).