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] andi + j < nReturn 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 <= 1040 <= nums[i] <= 1000nums[n - 1].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.
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`.
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.
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.
Time Complexity: O(n^2), where n is the number of elements.
Space Complexity: O(n), due to the use of a DP array.
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:
| Approach | Complexity |
|---|---|
| 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. |
| Dynamic Programming Approach | Time Complexity: O(n^2), where n is the number of elements. |
| Greedy Algorithm | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n²) | O(n) | When learning the state transition or explaining correctness before optimization |
| Greedy Range Expansion | O(n) | O(1) | Best general solution for interviews and large inputs |
Jump Game II - Greedy - Leetcode 45 - Python • NeetCode • 289,473 views views
Watch 9 more video solutions →Practice Jump Game II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor