TeachingBee

Jump Game 2 – Leetcode 45 Solution

Jump game 2

Problem Statement

The Jump Game 2 problem states Given an array of non-negative integers where each element represents the maximum number of steps you can take forward from that position. In other words, if you are at index ‘ i ‘, then nums[i] represents that you can jump to any nums[i + j] where:

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

Write a program to find the minimum number of jumps required to reach the end of the array (starting from the first element).

Constraints:

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

Example 1:

// Jump Game 2

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

Explanation:

Here we start at nums[0] = 2. From this position, the minimum jump we can take is 2 steps. So we jump one step which lands us at index 1 (nums[1] = 3). Then from index 1, the max jump is 3 which takes us to the last index. So the minimum jumps required is 2.

Example 2:

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

Discussed Solutions For Jump Game 2

  • Brute Force using recursion
  • Dp Solution Memoization
  • Dp solution Tabulation
  • Greedy Solution (Most optimised)

Recursion (Brute Force)

Intuition

Idea is to explore all possible jump paths from each position in the array and calculate the minimum number of jumps required to reach the end.

Approach

  1. Base Case:
    • If the start index is greater than or equal to the last index of the array, return 0 because no further jumps are needed.
  2. Recursive Case:
    • At each index, you have several choices: you can jump from 1 up to the number at that index.
    • For each choice, make a recursive call to find the minimum number of jumps needed from the index you jump to.
    • Add 1 to each result (for the jump you just made) and return the minimum of these results.
    • Finally, we return the minimum jumps calculated from the starting position (position 0). If it’s still positive infinity, it means there’s no way to reach the end. Otherwise, we return the minimum jumps required.
  3. Example:
    • Consider the array [2, 3, 1, 1, 4].
    • At index 0, you can jump 1 or 2 steps.
    • If you jump 1 step, you are at index 1, and you recursively find the minimum number of jumps from there.
    • If you jump 2 steps, you are at index 2, and you recursively find the minimum number of jumps from there.
    • Return the minimum of the results from the two choices, plus 1 for the jump you just made.
jump game 2 dry run
Jump Game 2 Dry Run

Code

C++

// C++ Implementation for Jump Game 2

#include <iostream>
#include <vector>

using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    return jumpRecursive(nums, 0);
}

int jumpRecursive(vector<int>& nums, int position) {
    int n = nums.size();
    if (position == n - 1) return 0;
    if (nums[position] == 0) return INT_MAX;

    int minJumps = INT_MAX;
    int maxJump = nums[position];

    for (int i = 1; i <= maxJump && position + i < n; i++) {
        int subJumps = jumpRecursive(nums, position + i);
        if (subJumps != INT_MAX) {
            minJumps = min(minJumps, 1 + subJumps);
        }
    }

    return minJumps;
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    int result = jump(nums);
    cout << result << endl;  // Output: 2
    return 0;
}

Java

// Java Implementation for Jump Game 2

public class JumpGameII {
    public int jump(int[] nums) {
        if (nums.length == 0) return 0;
        return jumpRecursive(nums, 0);
    }

    private int jumpRecursive(int[] nums, int position) {
        int n = nums.length;
        if (position == n - 1) return 0;
        if (nums[position] == 0) return Integer.MAX_VALUE;

        int minJumps = Integer.MAX_VALUE;
        int maxJump = nums[position];

        for (int i = 1; i <= maxJump && position + i < n; i++) {
            int subJumps = jumpRecursive(nums, position + i);
            if (subJumps != Integer.MAX_VALUE) {
                minJumps = Math.min(minJumps, 1 + subJumps);
            }
        }

        return minJumps;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        JumpGameII jumpGame = new JumpGameII();
        int result = jumpGame.jump(nums);
        System.out.println(result);  // Output: 2
    }
}

Python

// Python Implementation for Jump Game 2

def jump(nums):
    if len(nums) == 0:
        return 0
    return jumpRecursive(nums, 0)

def jumpRecursive(nums, position):
    n = len(nums)
    if position == n - 1:
        return 0
    if nums[position] == 0:
        return float('inf')

    min_jumps = float('inf')
    max_jump = nums[position]

    for i in range(1, max_jump + 1):
        if position + i < n:
            sub_jumps = jumpRecursive(nums, position + i)
            if sub_jumps != float('inf'):
                min_jumps = min(min_jumps, 1 + sub_jumps)

    return min_jumps

nums = [2, 3, 1, 1, 4]
result = jump(nums)
print(result)  # Output: 2

JavaScript

// C++ Implementation for Jump Game 2

function jump(nums) {
    if (nums.length === 0) return 0;
    return jumpRecursive(nums, 0);
}

function jumpRecursive(nums, position) {
    const n = nums.length;
    if (position === n - 1) return 0;
    if (nums[position] === 0) return Infinity;

    let minJumps = Infinity;
    const maxJump = nums[position];

    for (let i = 1; i <= maxJump && position + i < n; i++) {
        const subJumps = jumpRecursive(nums, position + i);
        if (subJumps !== Infinity) {
            minJumps = Math.min(minJumps, 1 + subJumps);
        }
    }

    return minJumps;
}

const nums = [2, 3, 1, 1, 4];
const result = jump(nums);
console.log(result);  // Output: 2

Analysis

  • The time complexity isO(2^n) or O(n!), that is there are n possible ways to move from an element for each element in the array.
  • Space complexity is O(n) – Recursive Call Stack

Dynamic Programming (Memoization)

Intuition

The memoization solution for the Jump Game II problem builds upon the recursive approach by adding a memoization table (also known as a memoization cache) to store and reuse the results of subproblems.

Code

C++

// C++ Implementation for Jump Game 2

#include <iostream>
#include <vector>

using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    vector<int> memo(n, -1);
    memo[0] = 0;
    return jumpRecursive(nums, 0, memo);
}

int jumpRecursive(vector<int>& nums, int position, vector<int>& memo) {
    if (memo[position] != -1) {
        return memo[position];
    }

    int n = nums.size();
    int minJumps = INT_MAX;
    int maxJump = nums[position];

    for (int i = 1; i <= maxJump && position + i < n; i++) {
        int subJumps = jumpRecursive(nums, position + i, memo);
        if (subJumps != INT_MAX) {
            minJumps = min(minJumps, 1 + subJumps);
        }
    }

    memo[position] = minJumps;
    return minJumps;
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    int result = jump(nums);
    cout << result << endl;  // Output: 2
    return 0;
}

Java

// Java Implementation for Jump Game 2

public class JumpGameII {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] memo = new int[n];
        for (int i = 0; i < n; i++) {
            memo[i] = -1;
        }
        memo[0] = 0;
        return jumpRecursive(nums, 0, memo);
    }

    private int jumpRecursive(int[] nums, int position, int[] memo) {
        if (memo[position] != -1) {
            return memo[position];
        }

        int n = nums.length;
        int minJumps = Integer.MAX_VALUE;
        int maxJump = nums[position];

        for (int i = 1; i <= maxJump && position + i < n; i++) {
            int subJumps = jumpRecursive(nums, position + i, memo);
            if (subJumps != Integer.MAX_VALUE) {
                minJumps = Math.min(minJumps, 1 + subJumps);
            }
        }

        memo[position] = minJumps;
        return minJumps;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        JumpGameII jumpGame = new JumpGameII();
        int result = jumpGame.jump(nums);
        System.out.println(result);  // Output: 2
    }
}

Python

// Python Implementation for Jump Game 2

def jump(nums):
    n = len(nums)
    memo = [-1] * n
    memo[0] = 0
    return jumpRecursive(nums, 0, memo)

def jumpRecursive(nums, position, memo):
    if memo[position] != -1:
        return memo[position]

    n = len(nums)
    min_jumps = float('inf')
    max_jump = nums[position]

    for i in range(1, max_jump + 1):
        if position + i < n:
            sub_jumps = jumpRecursive(nums, position + i, memo)
            if sub_jumps != float('inf'):
                min_jumps = min(min_jumps, 1 + sub_jumps)

    memo[position] = min_jumps
    return min_jumps

nums = [2, 3, 1, 1, 4]
result = jump(nums)
print(result)  # Output: 2

Javascript

// JavaScript Implementation for Jump Game 2

function jump(nums) {
    const n = nums.length;
    const memo = new Array(n).fill(-1);
    memo[0] = 0;
    return jumpRecursive(nums, 0, memo);
}

function jumpRecursive(nums, position, memo) {
    if (memo[position] !== -1) {
        return memo[position];
    }

    const n = nums.length;
    let minJumps = Infinity;
    const maxJump = nums[position];

    for (let i = 1; i <= maxJump && position + i < n; i++) {
        const subJumps = jumpRecursive(nums, position + i, memo);
        if (subJumps !== Infinity) {
            minJumps = Math.min(minJumps, 1 + subJumps);
        }
    }

    memo[position] = minJumps;
    return minJumps;
}

const nums = [2, 3, 1, 1, 4];
const result = jump(nums);
console.log(result);  // Output: 2

Analysis

  • The time complexity is O(n^2) or O(n^3)
  • Space complexity is O(n) – Memoization Table

Dynamic Programming (Tabulation)

Intuition

Like in memoization solution, we can break it down into smaller subproblems. The minimum jumps needed to reach a particular position depend on the minimum jumps needed to reach previous positions.The tabulation solution takes a bottom-up approach, starting from the beginning of the array and gradually building up the solution by considering the minimum jumps needed to reach each position. The table is initialized with a large value (e.g., infinity) except for the first position, which is initialized to 0 because it takes 0 jumps to reach itself.

Approach

We iterate through the positions in the array from left to right. For each position, we consider all possible jumps from the previous positions and update the minimum jumps required to reach the current position. After processing all positions, the value at the last position of the dynamic programming table represents the minimum jumps needed to reach the end of the array.

Code

C++

// C++ Implementation for Jump Game 2

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

using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);
    dp[0] = 0;  // It takes 0 jumps to reach the starting position.

    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= nums[i] && i + j < n; j++) {
            dp[i + j] = min(dp[i + j], dp[i] + 1);
        }
    }

    return dp[n - 1];
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    int result = jump(nums);
    cout << result << endl;  // Output: 2
    return 0;
}

Java

// Java Implementation for Jump Game 2

public class JumpGameII {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;  // It takes 0 jumps to reach the starting position.

        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= nums[i] && i + j < n; j++) {
                dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
            }
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        JumpGameII jumpGame = new JumpGameII();
        int result = jumpGame.jump(nums);
        System.out.println(result);  // Output: 2
    }
}

Python

// Python Implementation for Jump Game 2

def jump(nums):
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0  # It takes 0 jumps to reach the starting position.

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

    return dp[-1]

nums = [2, 3, 1, 1, 4]
result = jump(nums)
print(result)  # Output: 2

Javascript

// JavaScript Implementation for Jump Game 2

function jump(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(Infinity);
    dp[0] = 0;  // It takes 0 jumps to reach the starting position.

    for (let i = 0; i < n; i++) {
        for (let j = 1; j <= nums[i] && i + j < n; j++) {
            dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
        }
    }

    return dp[n - 1];
}

const nums = [2, 3, 1, 1, 4];
const result = jump(nums);
console.log(result);  // Output: 2

Analysis

  • The time complexity is O(n^2) or O(n^3)
  • Space complexity is O(n) – DP Table

Greedy

Intuition

The intuition behind this algorithm is to use a greedy approach to determine the minimum number of jumps required.

At each position, we calculate the farthest index we can reach from that position and update max_reach accordingly. When we reach the point where i is equal to max_reach, it means we need to make a jump to reach the farthest possible index with the current number of jumps.

Approach

  1. Initialize two variables: max_reach and steps. Set max_reach to 0 and steps to 0. max_reach represents the maximum index that can be reached with the current number of jumps, and steps represents the minimum number of jumps needed to reach the end.
  2. Iterate through the nums array from index 0 to len(nums) - 2 (the last index is excluded since we've already reached it if we're there).
  3. At each position i, update max_reach to be the maximum of its current value and i + nums[i]. This represents the farthest index reachable from the current position i.
  4. If i is equal to the current max_reach, it means we need to make a jump. Increment steps by 1 and update max_reach to the farthest index we can reach with the current number of jumps.
  5. Continue iterating through the array until you reach the last index.
  6. Return the steps as the minimum number of jumps needed to reach the end.

Code

C++

// C++ Implementation for Jump Game 2

#include <iostream>
#include <vector>

using namespace std;

int jump(vector<int>& nums) {
    int max_reach = 0;
    int steps = 0;
    int current_max_reach = 0;
    
    for (int i = 0; i < nums.size() - 1; i++) {
        current_max_reach = max(current_max_reach, i + nums[i]);
        
        if (i == max_reach) {
            max_reach = current_max_reach;
            steps++;
        }
    }
    
    return steps;
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    int result = jump(nums);
    cout << result << endl;  // Output: 2
    return 0;
}

Java

// Java Implementation for Jump Game 2

public class JumpGameII {
    public static int jump(int[] nums) {
        int maxReach = 0;
        int steps = 0;
        int currentMaxReach = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            currentMaxReach = Math.max(currentMaxReach, i + nums[i]);

            if (i == maxReach) {
                maxReach = currentMaxReach;
                steps++;
            }
        }

        return steps;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        int result = jump(nums);
        System.out.println(result);  // Output: 2
    }
}

Python

// Python Implementation for Jump Game 2

def jump(nums):
    max_reach = 0
    steps = 0
    current_max_reach = 0

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

        if i == max_reach:
            max_reach = current_max_reach
            steps += 1

    return steps

nums = [2, 3, 1, 1, 4]
result = jump(nums)
print(result)  # Output: 2

Javascript

// JavaScript Implementation for Jump Game 2

function jump(nums) {
    let maxReach = 0;
    let steps = 0;
    let currentMaxReach = 0;

    for (let i = 0; i < nums.length - 1; i++) {
        currentMaxReach = Math.max(currentMaxReach, i + nums[i]);

        if (i === maxReach) {
            maxReach = currentMaxReach;
            steps++;
        }
    }

    return steps;
}

const nums = [2, 3, 1, 1, 4];
const result = jump(nums);
console.log(result);  // Output: 2

Dry Run

Let’s dry run this algorithm by taking an example:

Consider the input array nums = [2, 3, 1, 1, 4].

Let’s go step by step through the algorithm:

  1. Initialize max_reach to 0 and steps to 0.
    • max_reach = 0
    • steps = 0
  2. Iteration 1 (i = 0): Start iterating through the array:
    • i = 0
    • max_reach = max(0, 0 + 2) = 2
    • Since i is equal to max_reach, we need to make a jump.
    • Increment steps by 1.
    • steps = 1
  3. Iteration 2 (i = 1):
    • i = 1
    • max_reach = max(2, 1 + 3) = 4
    • Since i is not equal to max_reach, we don’t need to make a jump.
  4. Iteration 3 (i = 2):
    • i = 2
    • max_reach = max(4, 2 + 1) = 4
    • Since i is not equal to max_reach, we don’t need to make a jump.
  5. Iteration 4 (i = 3):
    • i = 3
    • max_reach = max(4, 3 + 1) = 4
    • Since i is not equal to max_reach, we don’t need to make a jump.
  6. Iteration 5 (i = 4):
    • i = 4
    • max_reach = max(4, 4 + 4) = 8
    • Since i is equal to max_reach, we need to make a jump.
    • Increment steps by 1.
    • steps = 2
  7. Since we’ve reached the end. We don’t need to make any more jumps.
  8. Return steps, which is 2.

Analysis

  • The time complexity is Typically Linear (O(n log n) or O(n))
  • Space complexity is O(1) – Constant

Complexities For Different Jump Game 2 Solutions

ApproachTime ComplexitySpace Complexity
Recursive Brute ForceExponential (e.g., O(2^n) or O(n!))O(n) – Recursive Call Stack
Memoization (DP)Polynomial (e.g., O(n^2) or O(n^3))O(n) – Memoization Table
Tabulation (DP)Polynomial (e.g., O(n^2) or O(n^3))O(n) – DP Table
GreedyTypically Linear (O(n log n) or O(n))O(1) – Constant
Complexities For Different Jump Game 2 Solutions

Try out our free resume checker service where our Industry Experts will help you by providing resume score based on the key criteria that recruiters and hiring managers are looking for.

90% of Tech Recruiters Judge This In Seconds! 👩‍💻🔍

Don’t let your resume be the weak link. Discover how to make a strong first impression with our free technical resume review!

Related Articles

Hello World! in C HackerRank Solution 

Problem Statement In this challenge, we will learn some basic concepts of C that will get you started with the language. You will need to use the same syntax to

Why Aren’t You Getting Interview Calls? 📞❌

It might just be your resume. Let us pinpoint the problem for free and supercharge your job search. 

Newsletter

Don’t miss out! Subscribe now

Log In