How do you approach Jump Game?

Think greedily - track the farthest position you can reach.

What is the time complexity of Jump Game?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Jump Game?

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem. Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic. Missing the case where two greedy choices tie and the tiebreak decides correctness.

gitGood.dev

← Back to problems

Jump Game

MediumAlgorithms

Description

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.

Example 1

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

Output: true

Explanation: 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

Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints

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

Jump Game: approach, complexity and pitfalls

A medium greedy problem, graded against 6 test cases (3 of them hidden).

The pattern: Greedy

Take the locally best option each step and prove it stays globally optimal.

Reach for it when you see: Interval scheduling, jump/reachability questions, or an optimisation with an obvious local choice.

More Greedyproblems →

If you are stuck

Show the 3-step hint ladder

Think greedily - track the farthest position you can reach.
At each step, update the farthest reachable position.
If your current position exceeds the farthest reachable, you can't proceed.

The optimal approach

Show the approach: Greedy

Track the maximum reachable index. At each position, if we can reach it, update the maximum reach. If we can reach the end, return true.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Greedy mistakes

These apply to the pattern as a whole, not just this problem.

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem.
Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic.
Missing the case where two greedy choices tie and the tiebreak decides correctness.