Log inSign up
mediumLeetCodeNot Started

Jump Game

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index (0), 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 · Example 1: Reachable End:

Input: nums = [2, 3, 1, 1, 4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps from index 1 to the last index 4.

Example 2 · Example 2: Unreachable End:

Input: nums = [3, 2, 1, 0, 4]
Output: false
Explanation: All paths lead to index 3 with nums[3] = 0, where maxReach remains 3 < 4, making index 4 unreachable.

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why reaching an interval of indices allows greedy max reach tracking.
  • Recognize zero-traps in arrays and identify unreachable boundaries.
  • Implement the greedy solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Array of maximum jump steps.
  • Determine reachability of end index from start index.
  • No cost optimization, purely boolean reachability.

Algorithmic Decision Tree:

  • If boolean reachability -> Greedy furthest index tracking (O(N) time, O(1) space).
  • If minimum jumps required -> Jump Game II (Greedy level-by-level BFS).

Connected Patterns:

Jump Game IIVideo StitchingMinimum Number of Taps to Open to Water a Garden

1. Recursive Backtracking

Intuition

Recursively try every jump length from 1 to nums[pos] from the current position until the destination is reached or all paths fail.

Algorithm

  1. Step 1: If current position >= n - 1, return true.
  2. Step 2: Try every jump length from 1 up to nums[pos].
  3. Step 3: If any recursive call from pos + jump returns true, propagate true up.
  4. Step 4: If all jump choices fail, return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7 bool canJumpFrom(int pos, const vector<int>& nums) {
8 if (pos >= (int)nums.size() - 1) return true;
9 int furthest = min(pos + nums[pos], (int)nums.size() - 1);
10 for (int next = pos + 1; next <= furthest; ++next) {
11 if (canJumpFrom(next, nums)) return true;
12 }
13 return false;
14 }
15public:
16 bool canJump(vector<int>& nums) {
17 return canJumpFrom(0, nums);
18 }
19};
20
21int main() {
22 Solution sol;
23 vector<int> nums1 = {2, 3, 1, 1, 4};
24 vector<int> nums2 = {3, 2, 1, 0, 4};
25 cout << boolalpha;
26 cout << "nums1 reachable: " << sol.canJump(nums1) << endl;
27 cout << "nums2 reachable: " << sol.canJump(nums2) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Bottom-Up Dynamic Programming

Intuition

Maintain a boolean dp array where dp[i] indicates whether the end is reachable from index i. Iterate backwards from n - 2 down to 0.

Algorithm

  1. Step 1: Create a boolean array dp of size n. Set dp[n - 1] = true.
  2. Step 2: Iterate backwards from index i = n - 2 down to 0.
  3. Step 3: For index i, check each next index j from i + 1 up to min(i + nums[i], n - 1).
  4. Step 4: If any dp[j] is true, set dp[i] = true and break.
  5. Step 5: Return dp[0].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 bool canJump(vector<int>& nums) {
10 int n = nums.size();
11 vector<bool> dp(n, false);
12 dp[n - 1] = true;
13
14 for (int i = n - 2; i >= 0; --i) {
15 int furthest = min(i + nums[i], n - 1);
16 for (int j = i + 1; j <= furthest; ++j) {
17 if (dp[j]) {
18 dp[i] = true;
19 break;
20 }
21 }
22 }
23
24 return dp[0];
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> nums1 = {2, 3, 1, 1, 4};
31 vector<int> nums2 = {3, 2, 1, 0, 4};
32 cout << boolalpha;
33 cout << "nums1 reachable: " << sol.canJump(nums1) << endl;
34 cout << "nums2 reachable: " << sol.canJump(nums2) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

3. Greedy Furthest Reach Tracking

Intuition

Maintain the maximum reachable index maxReach while scanning from left to right. If the current index exceeds maxReach, return false.

Algorithm

  1. Step 1: Initialize maxReach = 0.
  2. Step 2: Iterate through each index i from 0 to n - 1.
  3. Step 3: If i > maxReach, index i is unreachable; return false.
  4. Step 4: Update maxReach = max(maxReach, i + nums[i]).
  5. Step 5: If maxReach >= n - 1, return true early.
  6. Step 6: Return true if loop finishes successfully.

Interactive Trace for Jump Game

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at index 0
Visual state
Values and pointers at this exact step
pointers
S
active
reachable
reachable
unreached
target
0
↑ i
1
2
↑ maxReach
3
4
Check / comparison
i <= maxReach (0 <= 0)
Decision / next transition
maxReach becomes 2.
Why this step matters

Step 1: Start at index 0. nums[0] = 2. maxReach = 0 + 2 = 2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 bool canJump(vector<int>& nums) {
10 int maxReach = 0;
11 int n = nums.size();
12
13 for (int i = 0; i < n; ++i) {
14 if (i > maxReach) return false;
15 maxReach = max(maxReach, i + nums[i]);
16 if (maxReach >= n - 1) return true;
17 }
18
19 return true;
20 }
21};
22
23int main() {
24 Solution sol;
25 vector<int> nums1 = {2, 3, 1, 1, 4};
26 vector<int> nums2 = {3, 2, 1, 0, 4};
27 cout << boolalpha;
28 cout << "nums1 reachable: " << sol.canJump(nums1) << endl;
29 cout << "nums2 reachable: " << sol.canJump(nums2) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Recursive BacktrackingO(2^N)O(N) call stackRecursively try every jump size from 1 up to nums[i] from the current index.Revisiting identical subproblems exponentially.
2.Better — Dynamic Programming (Memoization / Tabulation)O(N^2)O(N)DP[i] stores whether the end index is reachable from index i. Iterate backwards: DP[i] is true if any j in [i+1, min(i+nums[i], n-1)] has DP[j] == true.Inner loop testing jump targets.
3.Optimal — Greedy Max Reach TrackingOptimalO(N)O(1)Maintain maxReach. For each index i: if i > maxReach return false; otherwise maxReach = max(maxReach, i + nums[i]). If maxReach >= n - 1, return true early.Single linear scan.
Back to DSA Sheet