Skip to main content
Talentd

Jump Game II - Solution & Explanation

MediumArrayDynamic ProgrammingGreedy21 min readAsked at: Amazon, Microsoft, Apple +23
Practice this problem

Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

  • 0 <= j <= nums[i] and
  • i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

Approach Overview

Problem Overview: You are given an array where each element represents the maximum jump length from that position. Starting at index 0, the goal is to reach the last index using the minimum number of jumps. The challenge is choosing jumps that maximize reach while minimizing the total number of moves.

Approach 1: Dynamic Programming (O(n²) time, O(n) space)

The dynamic programming approach builds the answer bottom‑up. Create a dp array where dp[i] stores the minimum number of jumps required to reach index i. For every position i, iterate through all previous indices j and check if j + nums[j] >= i. If so, index i is reachable from j, so update dp[i] = min(dp[i], dp[j] + 1). This brute-force exploration of reachable states guarantees the optimal answer but requires nested iteration across the array. Time complexity is O(n²) with O(n) extra space for the DP array. This method is useful for understanding the transition logic before optimizing.

Approach 2: Greedy Range Expansion (O(n) time, O(1) space)

The optimal strategy treats the array like levels in a breadth-first traversal. While scanning the array, track two boundaries: the current jump range (currentEnd) and the farthest index reachable from any position in the current range (farthest). Iterate once through the array and update farthest = max(farthest, i + nums[i]). When the iteration reaches currentEnd, a jump must be taken, so increment the jump count and extend the range to farthest. This greedy choice works because expanding the reach as far as possible at each step minimizes the number of jump boundaries encountered. The algorithm runs in O(n) time and uses O(1) extra space.

The greedy technique relies on the same reachability idea used in the related array traversal problems but optimizes it with a single pass. It avoids computing results for every state like the dynamic programming approach.

Recommended for interviews: Interviewers typically expect the greedy solution. It demonstrates the ability to recognize range expansion and level-based traversal patterns, a common technique in greedy algorithms. Showing the DP approach first proves you understand the state transition and correctness, but optimizing it to the linear-time greedy method shows stronger problem-solving skill.

Approach 1: Greedy Approach

The greedy approach involves making a jump only when absolutely necessary. Track the maximum index you can reach at each step and make a decision to jump when you get to the maximum of the current window. This ensures the least number of jumps.

We maintain two variables: `farthest`, which tracks the farthest point reachable, and `currentEnd`, which tracks the end of the current jumping range. A jump is made when we reach `currentEnd`, which updates to `farthest`.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array, because we make a single pass through the array.
Space Complexity: O(1), since we are using a fixed amount of extra space.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

The dynamic programming approach calculates the minimum jumps required to reach each index. For each index, calculate the minimum number of jumps required from all previous indices that can reach the current index. However, this approach is less efficient in terms of time complexity.

Use an array `dp` to store the minimum number of jumps to reach each index. Initialize `dp[0]` with zero since no jumps are needed to reach it.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the number of elements.
Space Complexity: O(n), due to the use of a DP array.

Try this approach in the editor →

Approach 3: Greedy Algorithm

We can use a variable mx to record the farthest position that can be reached from the current position, a variable last to record the position of the last jump, and a variable ans to record the number of jumps.

Next, we traverse each position i in [0,..n - 2]. For each position i, we can calculate the farthest position that can be reached from the current position through i + nums[i]. We use mx to record this farthest position, that is, mx = max(mx, i + nums[i]). Then, we check whether the current position has reached the boundary of the last jump, that is, i = last. If it has reached, then we need to make a jump, update last to mx, and increase the number of jumps ans by 1.

Finally, we return the number of jumps ans.

The time complexity is O(n), where n is the length of the array. The space complexity is O(1).

Similar problems:

Code

PythonJavaC++GoTypeScriptRustC#CPHP

Python

Java

C++

Go

TypeScript

Rust

C#

C

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n), where n is the number of elements in the array, because we make a single pass through the array.
Space Complexity: O(1), since we are using a fixed amount of extra space.

Dynamic Programming Approach

Time Complexity: O(n^2), where n is the number of elements.
Space Complexity: O(n), due to the use of a DP array.

Greedy Algorithm—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic ProgrammingO(n²)O(n)When learning the state transition or explaining correctness before optimization
Greedy Range ExpansionO(n)O(1)Best general solution for interviews and large inputs

Video Solution

Jump Game II - Greedy - Leetcode 45 - Python • NeetCode • 301,502 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Jump Game II easy or hard?
Jump Game II is generally classified as a medium difficulty problem. The challenge is recognizing that a greedy range expansion strategy can replace the more intuitive dynamic programming solution, reducing the complexity from O(n^2) to O(n).
Jump Game II Python/Java solution
The greedy solution is commonly implemented in Python, Java, C++, JavaScript, and C#. It iterates through the array while updating the farthest reachable index and counts jumps whenever the traversal reaches the end of the current jump range. The same logic translates cleanly across languages with a single loop.
How to solve Jump Game II in O(n)?
Use a greedy traversal that keeps track of the farthest index reachable during the current jump window. Maintain two variables: the end of the current range and the farthest reachable index. When the loop index reaches the current range boundary, increment the jump count and extend the boundary to the farthest position discovered so far.
What is the best approach for Jump Game II?
The greedy range expansion approach is the most efficient solution. It scans the array once while tracking the farthest reachable index within the current jump range. Each time the iteration reaches the end of the current range, a jump is counted and the range expands. This achieves O(n) time complexity with O(1) extra space.
Is Jump Game II asked at Google/Amazon/Meta?
Jump Game II is a common interview problem at large tech companies because it tests greedy reasoning and array traversal optimization. Variants of the problem or related Jump Game questions have appeared in interviews at Amazon, Google, Meta, and Microsoft.
What data structure is used in Jump Game II?
The problem primarily uses array traversal. The dynamic programming approach introduces a DP array to store minimum jumps to each index, while the optimal greedy solution only uses a few integer variables to track range boundaries and the farthest reachable position.
What is the time complexity of Jump Game II?
The optimal greedy algorithm runs in O(n) time because each element is processed once while updating the farthest reachable position. A dynamic programming solution also exists but requires O(n^2) time since every index may check multiple previous positions to determine the minimum jumps.

Ready to solve this problem?

Practice Jump Game II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Jump Game

Next

Jump Game III