Jump Game II solution and explanation
Google
TCS
IBM
9 more videos on this problem
Jump Game II - Greedy - Leetcode 45 - PythonNeetCode · 11:58 · 301K views
L5. Jump Game - II | Greedy Algorithm Playlisttake U forward · 16:45 · 275K views
Jump Game 2 (LeetCode 45) | Minimum jumps to reach end of array | Explanation with AnimationsNikhil Lohia · 19:19 · 68K views
#Leetcode 45 Jump Game 2 || Code + Explanation + Example WalkthroughCode with Alisha · 12:42 · 66K views
Jump Game II | Live Coding with Explanation | Leetcode - 45Algorithms Made Easy · 9:38 · 28K views
Jump Game II - Leetcode 45 - Recursive Backtracking (Python)Greg Hogg · 9:37 · 14K views
Jump Game II - LeetCode 45 - Greedy Algorithm - Coding InterviewOne Code Man · 5:54 · 7K views
PASS the coding interview | #45 Jump Game II (Leetcode)Embersunn · 7:42 · 3K views
LeetCode 45: Jump Game II | Java Solution | Dynamic Programming & Greedy ApproachCode Scribbler · 8:13 · 847 views
Jump Game II Python Solution - LeetCode #45Professor Oakes · 5:09 · 501 views
The problem
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 < 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 <= 1040 <= 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.
class Solution:
def jump(self, nums):
jumps = 0
current_end = 0
farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumps
# Test
sol = Solution()
nums = [2, 3, 1, 1, 4]
print("Minimum jumps:", sol.jump(nums))class Solution {
public int jump(int[] nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 1, 4};
System.out.println("Minimum jumps: " + sol.jump(nums));
}
}#include <vector>
#include <iostream>
using namespace std;
int jump(vector<int>& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
int main() {
vector<int> nums = {2, 3, 1, 1, 4};
cout << "Minimum jumps: " << jump(nums) << endl;
return 0;
}function jump(nums) {
let jumps = 0, currentEnd = 0, farthest = 0;
for (let i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]);
if (i === currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
// Test
let nums = [2, 3, 1, 1, 4];
console.log("Minimum jumps: " + jump(nums));#include <stdio.h>
int jump(int* nums, int numsSize) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < numsSize - 1; i++) {
farthest = (farthest > i + nums[i]) ? farthest : i + nums[i];
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
int main() {
int nums[] = {2, 3, 1, 1, 4};
int length = sizeof(nums) / sizeof(nums[0]);
printf("Minimum jumps: %d\n", jump(nums, length));
return 0;
}public class Solution {
public int Jump(int[] nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.Length - 1; i++) {
farthest = Math.Max(farthest, i + nums[i]);
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
}
}
return jumps;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 1, 4};
Console.WriteLine("Minimum jumps: " + sol.Jump(nums));
}
}Through a single pass from the start to the end of the array, determine the `farthest` point reachable and adjust the jump point at `currentEnd`.
Time Complexity: O(n)
Space Complexity: O(1)
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.
class Solution:
def jump(self, nums):
dp = [float('inf')] * len(nums)
dp[0] = 0
for i in range(1, len(nums)):
for j in range(i):
if j + nums[j] >= i:
dp[i] = min(dp[i], dp[j] + 1)
return dp[-1]
# Test
sol = Solution()
nums = [2, 3, 1, 1, 4]
print("Minimum jumps:", sol.jump(nums))import java.util.Arrays;
class Solution {
public int jump(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.length - 1];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 1, 4};
System.out.println("Minimum jumps: " + sol.jump(nums));
}
}#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
int jump(vector<int>& nums) {
vector<int> dp(nums.size(), INT_MAX);
dp[0] = 0;
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (j + nums[j] >= i) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.size() - 1];
}
int main() {
vector<int> nums = {2, 3, 1, 1, 4};
cout << "Minimum jumps: " << jump(nums) << endl;
return 0;
}function jump(nums) {
const dp = new Array(nums.length).fill(Infinity);
dp[0] = 0;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (j + nums[j] >= i) {
dp[i] = Math.min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.length - 1];
}
// Test
let nums = [2, 3, 1, 1, 4];
console.log("Minimum jumps: " + jump(nums));#include <stdio.h>
#include <limits.h>
int jump(int* nums, int numsSize) {
int dp[numsSize];
for (int i = 0; i < numsSize; i++) {
dp[i] = INT_MAX;
}
dp[0] = 0;
for (int i = 1; i < numsSize; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i) {
dp[i] = dp[i] < dp[j] + 1 ? dp[i] : dp[j] + 1;
}
}
}
return dp[numsSize - 1];
}
int main() {
int nums[] = {2, 3, 1, 1, 4};
int length = sizeof(nums) / sizeof(nums[0]);
printf("Minimum jumps: %d\n", jump(nums, length));
return 0;
}using System;
public class Solution {
public int Jump(int[] nums) {
int[] dp = new int[nums.Length];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int i = 1; i < nums.Length; i++) {
for (int j = 0; j < i; j++) {
if (j + nums[j] >= i) {
dp[i] = Math.Min(dp[i], dp[j] + 1);
}
}
}
return dp[nums.Length - 1];
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 1, 4};
Console.WriteLine("Minimum jumps: " + sol.Jump(nums));
}
}Create a DP array initialized with infinity to store the minimum number of jumps for each index. Update for each reachable index from previous positions.
Time Complexity: O(n^2)
Space Complexity: O(n)
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:
function jump(nums: number[]): number {
let [ans, mx, last] = [0, 0, 0];
for (let i = 0; i < nums.length - 1; ++i) {
mx = Math.max(mx, i + nums[i]);
if (last === i) {
++ans;
last = mx;
}
}
return ans;
}func jump(nums []int) (ans int) {
mx, last := 0, 0
for i, x := range nums[:len(nums)-1] {
mx = max(mx, i+x)
if last == i {
ans++
last = mx
}
}
return
}impl Solution {
pub fn jump(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut mx = 0;
let mut last = 0;
for i in 0..(nums.len() - 1) {
mx = mx.max(i as i32 + nums[i]);
if last == i as i32 {
ans += 1;
last = mx;
}
}
ans
}
}class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function jump($nums) {
$ans = 0;
$mx = 0;
$last = 0;
for ($i = 0; $i < count($nums) - 1; $i++) {
$mx = max($mx, $i + $nums[$i]);
if ($last == $i) {
$ans++;
$last = $mx;
}
}
return $ans;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n) |
| Dynamic Programming Approach | Time Complexity: O(n^2) |
| Greedy Algorithm | – |
Complexity analysis
| 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 |
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.