Jump Game II

Problem Statement

Given an integer array nums where you are initially positioned at the array’s first index, and each element in the array represents your maximum jump length from that position, determine the minimum number of jumps you need to make to reach the last index.

You are guaranteed that you can always reach the last index.

What to notice first

• You start at index 0 and must reach the last index, returning the count of jumps.
• Each nums[i] tells you the maximum distance you can jump from index i.
• The key insight is that you want to extend your reachable range as far as possible with each jump, not jump to a specific target.
• A greedy approach works: always jump when you must, not before.

Examples

Input	Output	Explanation
[2, 3, 1, 1, 4]	2	Jump to index 1, then jump 3 steps to the last index.
[2, 3, 0, 6, 9, 1, 2]	3	Jump to index 1, then to index 3 or 4 (from either you can reach 6), then to index 6.
[10]	0	Already at the last index.
[1, 1, 1, 0]	3	Must jump once from each index because you can only jump 1 step at a time.

Constraints

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 1000
• It is guaranteed that you can always reach nums.length - 1.

Real-World Applications

Where this pattern appears

• Mobile robot navigation — determine minimum number of directional commands to move from start to goal, where each command can move a variable distance.
• Video game level progression — calculate minimum jumps on moving platforms where each platform extends your reach by a certain amount.
• Network packet routing — find minimum hops between routers, where each router can forward to a set of neighbors within its range.
• Resource batching in distributed systems — minimize API calls needed to fetch data across multiple servers, where each call can fetch a certain amount.

Complexity Comparison

Approach	Time	Space	Key Insight	Best When
Greedy Min Jumps	O(n)	O(1)	Always extend reach as far as possible before jumping	General case — optimal and simple
Dynamic Programming	O(n²)	O(n)	Compute minimum jumps to each position, then look back	Interview deep dive / illustrating DP pattern

Which approach should you learn first?

• Pick Greedy Min Jumps if you want the optimal, elegant solution that works in linear time.
• Pick Dynamic Programming if you want to understand the foundational DP pattern (though it is slower).

Best For Speed

Greedy Min Jumps

O(n) time · O(1) space

Foundational Pattern

Dynamic Programming

O(n²) time · O(n) space

Approach 1: Greedy Min Jumps (Recommended)

★ Recommended

Maintain a current_end that represents the farthest index reachable with the current number of jumps. When you reach current_end, you must jump, and you extend your reach to farthest—the farthest index you saw while scanning up to current_end.

Key insight: You don’t decide where to jump to. Instead, you scan ahead to see how far you can go, then commit to jumping when you exhaust your current range.

⏱ Time O(n) Single pass 💾 Space O(1) Two pointers

Step-by-step Example

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

Step	i	nums[i]	Reach from i	current_end	farthest	Action
1	0	2	0+2=2	0	2	i==current_end → jump (jumps=1, current_end=2)
2	1	3	1+3=4	2	4	farthest updated to 4
3	2	1	2+1=3	2	4	i==current_end → jump (jumps=2, current_end=4)
4	3	1	3+1=4	4	4	current_end>=len-1 → done

Result: jumps = 2 ✓

Input: nums = [2, 3, 0, 6, 9, 1, 2]

Step	i	nums[i]	Reach from i	current_end	farthest	Action
1	0	2	0+2=2	0	2	i==current_end → jump (jumps=1, current_end=2)
2	1	3	1+3=4	2	4	farthest updated to 4
3	2	0	2+0=2	2	4	i==current_end → jump (jumps=2, current_end=4)
4	3	6	3+6=9	4	9	farthest updated to 9
5	4	9	4+9=13	4	13	current_end>=len-1 → done

Result: jumps = 2 ✓

Animated walkthrough

How the greedy min jumps solution counts jumps

Watch how current_end expands and farthest extends. When you reach current_end, you must jump and adopt farthest as your new range.

Back Autoplay Next Reset

Step 1 of 7

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function jumpGameIIGreedy(nums):
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0    // End of range reachable with current jumps
    farthest = 0       // Farthest index reachable so far

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps++
            current_end = farthest

            if current_end >= len(nums) - 1:
                break

    return jumps

Solution Code

Python

jump_game_ii_greedy.py

from typing import List


def jump_game_ii_greedy(nums: List[int]) -> int:
    """
    Greedy approach: track the farthest reachable index and jump count.

    Intuition: We maintain the range [current_start, current_end] that can be reached
    with the current number of jumps. When we exhaust this range, we increment jumps
    and expand to [current_end + 1, farthest], which is reachable with one more jump.

    Time Complexity: O(n) - single pass through array
    Space Complexity: O(1) - only use constant extra space
    """
    if len(nums) <= 1:
        return 0

    jumps = 0
    current_end = 0  # End of range reachable with current number of jumps
    farthest = 0     # Farthest index reachable so far

    for i in range(len(nums) - 1):  # No need to check the last index
        # Update the farthest index we can reach
        farthest = max(farthest, i + nums[i])

        # If we've reached the end of current jump range, we must jump
        if i == current_end:
            jumps += 1
            current_end = farthest

            # Optimization: if we can reach the end, no need to continue
            if current_end >= len(nums) - 1:
                break

    return jumps


# Test cases
print(jump_game_ii_greedy([2, 3, 1, 1, 4]))     # 2 (0->1->4)
print(jump_game_ii_greedy([2, 3, 0, 6, 9, 1, 2]))  # 3 (0->1->3/4->6)
print(jump_game_ii_greedy([10]))                # 0 (already at end)
print(jump_game_ii_greedy([1, 1, 1, 0]))        # 3 (must jump 1 step at a time)

C++

jump_game_ii_greedy.cpp

#include <iostream>
#include <vector>
#include <algorithm>

int jumpGameIIGreedy(std::vector<int>& nums) {
    /*
    Greedy approach: track the farthest reachable index and jump count.

    Intuition: We maintain the range [current_start, current_end] that can be reached
    with the current number of jumps. When we exhaust this range, we increment jumps
    and expand to [current_end + 1, farthest], which is reachable with one more jump.

    Time Complexity: O(n) - single pass through array
    Space Complexity: O(1) - only use constant extra space
    */
    if (nums.size() <= 1) {
        return 0;
    }

    int jumps = 0;
    int currentEnd = 0;   // End of range reachable with current number of jumps
    int farthest = 0;     // Farthest index reachable so far

    for (int i = 0; i < (int)nums.size() - 1; ++i) {
        // Update the farthest index we can reach
        farthest = std::max(farthest, i + nums[i]);

        // If we've reached the end of current jump range, we must jump
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;

            // Optimization: if we can reach the end, no need to continue
            if (currentEnd >= (int)nums.size() - 1) {
                break;
            }
        }
    }

    return jumps;
}

int main() {
    std::vector<int> test1 = {2, 3, 1, 1, 4};
    std::cout << jumpGameIIGreedy(test1) << std::endl;  // 2

    std::vector<int> test2 = {2, 3, 0, 6, 9, 1, 2};
    std::cout << jumpGameIIGreedy(test2) << std::endl;  // 2

    std::vector<int> test3 = {10};
    std::cout << jumpGameIIGreedy(test3) << std::endl;  // 0

    std::vector<int> test4 = {1, 1, 1, 0};
    std::cout << jumpGameIIGreedy(test4) << std::endl;  // 3

    return 0;
}

Java

jump_game_ii_greedy.java

class JumpGameIIGreedy {
    /**
     * Greedy approach: track the farthest reachable index and jump count.
     *
     * Intuition: We maintain the range [currentEnd] that can be reached
     * with the current number of jumps. When we exhaust this range, we increment jumps
     * and expand to [currentEnd + 1, farthest], which is reachable with one more jump.
     *
     * Time Complexity: O(n) - single pass through array
     * Space Complexity: O(1) - only use constant extra space
     */
    public static int jumpGameIIGreedy(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        int jumps = 0;
        int currentEnd = 0;   // End of range reachable with current number of jumps
        int farthest = 0;     // Farthest index reachable so far

        for (int i = 0; i < nums.length - 1; i++) {
            // Update the farthest index we can reach
            farthest = Math.max(farthest, i + nums[i]);

            // If we've reached the end of current jump range, we must jump
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;

                // Optimization: if we can reach the end, no need to continue
                if (currentEnd >= nums.length - 1) {
                    break;
                }
            }
        }

        return jumps;
    }

    public static void main(String[] args) {
        System.out.println(jumpGameIIGreedy(new int[]{2, 3, 1, 1, 4}));        // 2
        System.out.println(jumpGameIIGreedy(new int[]{2, 3, 0, 6, 9, 1, 2}));  // 2
        System.out.println(jumpGameIIGreedy(new int[]{10}));                   // 0
        System.out.println(jumpGameIIGreedy(new int[]{1, 1, 1, 0}));           // 3
    }
}

JavaScript

jump_game_ii_greedy.js

/**
 * Greedy approach: track the farthest reachable index and jump count.
 *
 * Intuition: We maintain the range [currentEnd] that can be reached
 * with the current number of jumps. When we exhaust this range, we increment jumps
 * and expand to [currentEnd + 1, farthest], which is reachable with one more jump.
 *
 * Time Complexity: O(n) - single pass through array
 * Space Complexity: O(1) - only use constant extra space
 *
 * @param {number[]} nums - The array of jump values
 * @return {number} - Minimum number of jumps to reach the last index
 */
function jumpGameIIGreedy(nums) {
    if (nums.length <= 1) {
        return 0;
    }

    let jumps = 0;
    let currentEnd = 0;   // End of range reachable with current number of jumps
    let farthest = 0;     // Farthest index reachable so far

    for (let i = 0; i < nums.length - 1; i++) {
        // Update the farthest index we can reach
        farthest = Math.max(farthest, i + nums[i]);

        // If we've reached the end of current jump range, we must jump
        if (i === currentEnd) {
            jumps++;
            currentEnd = farthest;

            // Optimization: if we can reach the end, no need to continue
            if (currentEnd >= nums.length - 1) {
                break;
            }
        }
    }

    return jumps;
}

// Test cases
console.log(jumpGameIIGreedy([2, 3, 1, 1, 4]));        // 2
console.log(jumpGameIIGreedy([2, 3, 0, 6, 9, 1, 2]));  // 3
console.log(jumpGameIIGreedy([10]));                   // 0
console.log(jumpGameIIGreedy([1, 1, 1, 0]));           // 3

export default jumpGameIIGreedy;

Rust

jump_game_ii_greedy.rs

/// Greedy approach: track the farthest reachable index and jump count.
///
/// Intuition: We maintain the range [current_end] that can be reached
/// with the current number of jumps. When we exhaust this range, we increment jumps
/// and expand to [current_end + 1, farthest], which is reachable with one more jump.
///
/// Time Complexity: O(n) - single pass through array
/// Space Complexity: O(1) - only use constant extra space
pub fn jump_game_ii_greedy(nums: Vec<i32>) -> i32 {
    if nums.len() <= 1 {
        return 0;
    }

    let mut jumps = 0;
    let mut current_end = 0;  // End of range reachable with current number of jumps
    let mut farthest = 0;      // Farthest index reachable so far

    for i in 0..nums.len() - 1 {
        // Update the farthest index we can reach
        farthest = std::cmp::max(farthest, i as i32 + nums[i]) as usize;

        // If we've reached the end of current jump range, we must jump
        if i == current_end {
            jumps += 1;
            current_end = farthest;

            // Optimization: if we can reach the end, no need to continue
            if current_end >= nums.len() - 1 {
                break;
            }
        }
    }

    jumps
}

fn main() {
    println!("{}", jump_game_ii_greedy(vec![2, 3, 1, 1, 4]));        // 2
    println!("{}", jump_game_ii_greedy(vec![2, 3, 0, 6, 9, 1, 2]));  // 2
    println!("{}", jump_game_ii_greedy(vec![10]));                   // 0
    println!("{}", jump_game_ii_greedy(vec![1, 1, 1, 0]));           // 3
}

Go

jump_game_ii_greedy.go

package main

import "fmt"

// Greedy approach: track the farthest reachable index and jump count.
//
// Intuition: We maintain the range [currentEnd] that can be reached
// with the current number of jumps. When we exhaust this range, we increment jumps
// and expand to [currentEnd + 1, farthest], which is reachable with one more jump.
//
// Time Complexity: O(n) - single pass through array
// Space Complexity: O(1) - only use constant extra space
func jumpGameIIGreedy(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }

    jumps := 0
    currentEnd := 0  // End of range reachable with current number of jumps
    farthest := 0    // Farthest index reachable so far

    for i := 0; i < len(nums)-1; i++ {
        // Update the farthest index we can reach
        if i+nums[i] > farthest {
            farthest = i + nums[i]
        }

        // If we've reached the end of current jump range, we must jump
        if i == currentEnd {
            jumps++
            currentEnd = farthest

            // Optimization: if we can reach the end, no need to continue
            if currentEnd >= len(nums)-1 {
                break
            }
        }
    }

    return jumps
}

func main() {
    fmt.Println(jumpGameIIGreedy([]int{2, 3, 1, 1, 4}))        // 2
    fmt.Println(jumpGameIIGreedy([]int{2, 3, 0, 6, 9, 1, 2}))  // 2
    fmt.Println(jumpGameIIGreedy([]int{10}))                   // 0
    fmt.Println(jumpGameIIGreedy([]int{1, 1, 1, 0}))           // 3
}

Approach 2: Dynamic Programming

🎯 Interview Favourite

Compute the minimum number of jumps needed to reach each index by looking back at all indices that can reach the current index, and taking the minimum.

For each index i, check all previous indices j where j + nums[j] >= i. Any such j can reach i in one jump. The minimum jumps to reach i is 1 + min(jumps to reach j).

Slower but instructive

This DP approach is O(n²) and slower than the greedy approach. It is useful for understanding the foundational DP pattern and for problems with additional constraints (like jump count limits).

⏱ Time O(n²) Nested loops 💾 Space O(n) DP array

Step-by-step Example

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

i	j ranges that reach i	min(dp[j] + 1)	dp[i]
0	—	—	0 (start)
1	j=0: 0+2>=1 ✓	dp[0]+1 = 1	1
2	j=0: 0+2>=2 ✓	dp[0]+1 = 1	1
3	j=1: 1+3>=3 ✓	dp[1]+1 = 2	2
4	j=1: 1+3>=4 ✓	dp[1]+1 = 2	2

Result: dp[4] = 2 ✓

Pseudocode

function jumpGameIIDP(nums):
    if len(nums) <= 1:
        return 0

    n = len(nums)
    dp = [infinity] * n
    dp[0] = 0

    for i in range(1, n):
        for j in range(i):
            if j + nums[j] >= i:
                dp[i] = min(dp[i], dp[j] + 1)
                break

    return dp[n - 1]

Solution Code

Python

jump_game_ii_dp.py

from typing import List


def jump_game_ii_dp(nums: List[int]) -> int:
    """
    Dynamic Programming approach: compute minimum jumps needed to reach each index.

    Intuition: dp[i] = minimum number of jumps to reach index i.
    For each index i, look back at all indices j where j + nums[j] >= i,
    meaning from j we can reach i in one jump. Take the minimum jumps[j] + 1.

    Time Complexity: O(n²) - for each index, we may check all previous indices
    Space Complexity: O(n) - dp array

    This approach is less efficient than greedy but illustrates the classic DP pattern.
    """
    if len(nums) <= 1:
        return 0

    n = len(nums)
    # dp[i] = minimum jumps needed to reach index i
    dp = [float('inf')] * n
    dp[0] = 0  # Start at index 0 with 0 jumps

    for i in range(1, n):
        # Check all previous indices to see which can reach i
        for j in range(i):
            if j + nums[j] >= i:  # From index j, we can reach index i
                dp[i] = min(dp[i], dp[j] + 1)
                break  # Optimization: since we want minimum, once we find a j that reaches i, we can stop

    return dp[n - 1]


# Test cases
print(jump_game_ii_dp([2, 3, 1, 1, 4]))        # 2
print(jump_game_ii_dp([2, 3, 0, 6, 9, 1, 2]))  # 3
print(jump_game_ii_dp([10]))                   # 0
print(jump_game_ii_dp([1, 1, 1, 0]))           # 3

C++

jump_game_ii_dp.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

int jumpGameIIDP(std::vector<int>& nums) {
    /*
    Dynamic Programming approach: compute minimum jumps needed to reach each index.

    Intuition: dp[i] = minimum number of jumps to reach index i.
    For each index i, look back at all indices j where j + nums[j] >= i,
    meaning from j we can reach i in one jump. Take the minimum jumps[j] + 1.

    Time Complexity: O(n²) - for each index, we may check all previous indices
    Space Complexity: O(n) - dp array
    */
    if (nums.size() <= 1) {
        return 0;
    }

    int n = nums.size();
    std::vector<int> dp(n, INT_MAX);
    dp[0] = 0;  // Start at index 0 with 0 jumps

    for (int i = 1; i < n; ++i) {
        // Check all previous indices to see which can reach i
        for (int j = 0; j < i; ++j) {
            if (j + nums[j] >= i) {  // From index j, we can reach index i
                dp[i] = std::min(dp[i], dp[j] + 1);
                break;  // Optimization: once we find a j that reaches i, we can stop
            }
        }
    }

    return dp[n - 1];
}

int main() {
    std::vector<int> test1 = {2, 3, 1, 1, 4};
    std::cout << jumpGameIIDP(test1) << std::endl;  // 2

    std::vector<int> test2 = {2, 3, 0, 6, 9, 1, 2};
    std::cout << jumpGameIIDP(test2) << std::endl;  // 2

    std::vector<int> test3 = {10};
    std::cout << jumpGameIIDP(test3) << std::endl;  // 0

    std::vector<int> test4 = {1, 1, 1, 0};
    std::cout << jumpGameIIDP(test4) << std::endl;  // 3

    return 0;
}

Java

jump_game_ii_dp.java

class JumpGameIIDP {
    /**
     * Dynamic Programming approach: compute minimum jumps needed to reach each index.
     *
     * Intuition: dp[i] = minimum number of jumps to reach index i.
     * For each index i, look back at all indices j where j + nums[j] >= i,
     * meaning from j we can reach i in one jump. Take the minimum jumps[j] + 1.
     *
     * Time Complexity: O(n²) - for each index, we may check all previous indices
     * Space Complexity: O(n) - dp array
     */
    public static int jumpGameIIDP(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        int n = nums.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;  // Start at index 0 with 0 jumps

        for (int i = 1; i < n; i++) {
            // Check all previous indices to see which can reach i
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {  // From index j, we can reach index i
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                    break;  // Optimization: once we find a j that reaches i, we can stop
                }
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        System.out.println(jumpGameIIDP(new int[]{2, 3, 1, 1, 4}));        // 2
        System.out.println(jumpGameIIDP(new int[]{2, 3, 0, 6, 9, 1, 2}));  // 2
        System.out.println(jumpGameIIDP(new int[]{10}));                   // 0
        System.out.println(jumpGameIIDP(new int[]{1, 1, 1, 0}));           // 3
    }
}

JavaScript

jump_game_ii_dp.js

/**
 * Dynamic Programming approach: compute minimum jumps needed to reach each index.
 *
 * Intuition: dp[i] = minimum number of jumps to reach index i.
 * For each index i, look back at all indices j where j + nums[j] >= i,
 * meaning from j we can reach i in one jump. Take the minimum jumps[j] + 1.
 *
 * Time Complexity: O(n²) - for each index, we may check all previous indices
 * Space Complexity: O(n) - dp array
 *
 * @param {number[]} nums - The array of jump values
 * @return {number} - Minimum number of jumps to reach the last index
 */
function jumpGameIIDP(nums) {
    if (nums.length <= 1) {
        return 0;
    }

    const n = nums.length;
    const dp = Array(n).fill(Infinity);
    dp[0] = 0;  // Start at index 0 with 0 jumps

    for (let i = 1; i < n; i++) {
        // Check all previous indices to see which can reach i
        for (let j = 0; j < i; j++) {
            if (j + nums[j] >= i) {  // From index j, we can reach index i
                dp[i] = Math.min(dp[i], dp[j] + 1);
                break;  // Optimization: once we find a j that reaches i, we can stop
            }
        }
    }

    return dp[n - 1];
}

// Test cases
console.log(jumpGameIIDP([2, 3, 1, 1, 4]));        // 2
console.log(jumpGameIIDP([2, 3, 0, 6, 9, 1, 2]));  // 3
console.log(jumpGameIIDP([10]));                   // 0
console.log(jumpGameIIDP([1, 1, 1, 0]));           // 3

export default jumpGameIIDP;

Rust

jump_game_ii_dp.rs

/// Dynamic Programming approach: compute minimum jumps needed to reach each index.
///
/// Intuition: dp[i] = minimum number of jumps to reach index i.
/// For each index i, look back at all indices j where j + nums[j] >= i,
/// meaning from j we can reach i in one jump. Take the minimum jumps[j] + 1.
///
/// Time Complexity: O(n²) - for each index, we may check all previous indices
/// Space Complexity: O(n) - dp array
pub fn jump_game_ii_dp(nums: Vec<i32>) -> i32 {
    if nums.len() <= 1 {
        return 0;
    }

    let n = nums.len();
    let mut dp = vec![i32::MAX; n];
    dp[0] = 0;  // Start at index 0 with 0 jumps

    for i in 1..n {
        // Check all previous indices to see which can reach i
        for j in 0..i {
            if j as i32 + nums[j] >= i as i32 {  // From index j, we can reach index i
                dp[i] = std::cmp::min(dp[i], dp[j] + 1);
                break;  // Optimization: once we find a j that reaches i, we can stop
            }
        }
    }

    dp[n - 1]
}

fn main() {
    println!("{}", jump_game_ii_dp(vec![2, 3, 1, 1, 4]));        // 2
    println!("{}", jump_game_ii_dp(vec![2, 3, 0, 6, 9, 1, 2]));  // 2
    println!("{}", jump_game_ii_dp(vec![10]));                   // 0
    println!("{}", jump_game_ii_dp(vec![1, 1, 1, 0]));           // 3
}

Go

jump_game_ii_dp.go

package main

import (
    "fmt"
    "math"
)

// Dynamic Programming approach: compute minimum jumps needed to reach each index.
//
// Intuition: dp[i] = minimum number of jumps to reach index i.
// For each index i, look back at all indices j where j + nums[j] >= i,
// meaning from j we can reach i in one jump. Take the minimum jumps[j] + 1.
//
// Time Complexity: O(n²) - for each index, we may check all previous indices
// Space Complexity: O(n) - dp array
func jumpGameIIDP(nums []int) int {
    if len(nums) <= 1 {
        return 0
    }

    n := len(nums)
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = int(math.MaxInt32)
    }
    dp[0] = 0  // Start at index 0 with 0 jumps

    for i := 1; i < n; i++ {
        // Check all previous indices to see which can reach i
        for j := 0; j < i; j++ {
            if j+nums[j] >= i {  // From index j, we can reach index i
                if dp[j]+1 < dp[i] {
                    dp[i] = dp[j] + 1
                }
                break  // Optimization: once we find a j that reaches i, we can stop
            }
        }
    }

    return dp[n-1]
}

func main() {
    fmt.Println(jumpGameIIDP([]int{2, 3, 1, 1, 4}))        // 2
    fmt.Println(jumpGameIIDP([]int{2, 3, 0, 6, 9, 1, 2}))  // 2
    fmt.Println(jumpGameIIDP([]int{10}))                   // 0
    fmt.Println(jumpGameIIDP([]int{1, 1, 1, 0}))           // 3
}

Common mistakes

Watch for these pitfalls

• Returning the jump count of a specific position instead of the final index. Always jump to the last index, not a specific intermediate target.
• Confusing this with Jump Game I (problem #55). Problem #55 asks only whether you can reach the end, not the minimum number of jumps. Problem #45 requires you to return the count.
• Forgetting the edge case where the array has only one element. If you are already at the last index, the answer is 0.
• Greedy pitfall: Jumping too early. The greedy approach jumps only when necessary, not whenever possible.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

jump_game_ii_space_optimized.py

"""
Solution for Jump Game II
"""

def solve():
    """Implementation for approach 3 of Jump Game II"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

jump_game_ii_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Jump Game II
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

JumpGameIiSpaceOptimized.java

/**
 * Solution for Jump Game II
 * Approach 3
 */
public class JumpGameIiSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

jump_game_ii_space_optimized.js

/**
 * Solution for Jump Game II
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

jump_game_ii_space_optimized.rs

/// Solution for Jump Game II
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

jump_game_ii_space_optimized.go

package main

import "fmt"

// Solution for Jump Game II
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Jump Game ↗ Medium #55
• Jump Game III ↗ Medium #1306
• Jump Game VII ↗ Medium #1871
• Best Time to Buy and Sell Stock II ↗ Medium #122

Interview Tips

Key trade-offs to discuss

• Why greedy over DP? The greedy approach is O(n) vs O(n²), a dramatic difference. The key insight is that you don’t need to examine all predecessors; you only need to know the farthest reach so far.
• Why not brute force? Brute force (trying all possible jump sequences) is exponential. DP and greedy both prune the search space significantly.
• Jump vs reachability: Clarify with your interviewer: Jump Game I asks “can you reach the end?”, while Jump Game II asks “what is the minimum jumps?” The solutions are different.
• Extension: What if each element could be negative (representing a penalty or boundary)? What if you could jump backward? These variants change the problem structure.
• Edge cases: Single element array, array where all elements are 0 except the first, arrays where you can jump very far (only 1 jump needed).

← Previous
#44 Wildcard Matching Next
#46 Permutations →