Jump Game 2 - Get min jumps | K5kC

Problem

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

Examples

Example 1:

1
2
3


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:

1
2


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

This is an extension of Jump Game 1 - Check if it reaches last index

Solution

We have already seen Jump Game 1 - Check if it reaches last index. We have a DP solution, but greedy solution is optimal with O(n).

Method 1 - Recursion

The problem can be solved using recursion by trying out each possible jump at each position and recursively calculating the minimum jumps required:

Start from index 0 and explore each possible jump based on the current value.
For each jump, recurse and calculate the minimum jumps required from the new index.
Use base cases to minimize recursion:
1. If the start index is the same as the end index, return 0 (no more jumps needed).
2. If the value at the start index is 0, return Integer.MAX_VALUE (can’t move further).
3. If the remaining length can be covered in one jump, return 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


public class Solution {

    public int jump(int[] nums, int startIndex) {
        // If reached the end, return 0
        if (startIndex == nums.length - 1) {
            return 0;
        }
        
        int size = nums.length;
        int remainingLength = size - startIndex;

        // If the remaining length can be covered in one jump, return 1
        if (remainingLength <= nums[startIndex]) {
            return 1;
        }

        // If current position is zero, can't move further
        if (nums[startIndex] == 0) {
            System.out.println("Cannot move further");
            return Integer.MAX_VALUE;
        }

        int jumps = Integer.MAX_VALUE;

        // Try every jump length from 1 to nums[startIndex]
        for (int i = 1; i <= nums[startIndex]; i++) {
            int temp = jump(nums, startIndex + i);
            if (temp != Integer.MAX_VALUE) {
                jumps = Math.min(jumps, 1 + temp);
            }
        }
        
        return jumps;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    def jump(self, nums: List[int], start: int) -> int:
        # If reached the end, return 0
        if start == len(nums) - 1:
            return 0
        
        size = len(nums)
        remaining_length = size - start

        # If remaining length can be covered in one jump, return 1
        if remaining_length <= nums[start]:
            return 1
        
        # If current position is zero, can't move further
        if nums[start] == 0:
            print("Cannot move further")
            return float('inf')
        
        jumps = float('inf')

        # Try every jump length from 1 to nums[start]
        for i in range(1, nums[start] + 1):
            temp = self.jump(nums, start + i)
            if temp != float('inf'):
                jumps = min(jumps, 1 + temp)
        
        return jumps

Complexity

⏰ Time complexity: O(2^n), where n is the length of the array in the worst case, due to exponential growth from each recursive call.
🧺 Space complexity: O(n), due to the maximum depth of the recursion stack.

Method 2 - Using Top Down Dynamic Programming

We observe that many subproblems are solved multiple times in the purely recursive approach. By using dynamic programming and memoization, we can store the results of these subproblems and use the stored results instead of recomputing them, thereby optimizing our solution.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


public class Solution {

    HashMap<Integer, Integer> memo = new HashMap<>();

    private int jump(int[] nums, int startIndex) {
        // If reached the end, return 0
        if (startIndex == nums.length - 1) {
            return 0;
        }

        // If the result is already computed, use it
        if (memo.containsKey(startIndex)) {
            return memo.get(startIndex);
        }

        int size = nums.length;
        int remainingLength = size - startIndex;

        // If remaining length can be covered in one jump, return 1
        if (remainingLength <= nums[startIndex]) {
            return 1;
        }

        // If current position is zero, can't move further
        if (nums[startIndex] == 0) {
            return Integer.MAX_VALUE;
        }

        int jumps = Integer.MAX_VALUE;

        // Try every jump length from 1 to nums[startIndex]
        for (int i = 1; i <= nums[startIndex]; i++) {
            int temp = jump(nums, startIndex + i);
            if (temp != Integer.MAX_VALUE) {
                jumps = Math.min(jumps, 1 + temp);
            }
        }

        memo.put(startIndex, jumps);
        return jumps;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution:
    def __init__(self):
        self.memo: Dict[int, int] = {}

    def jump(self, nums: List[int], start: int = 0) -> int:
        # If reached the end, return 0
        if start == len(nums) - 1:
            return 0
        
        # If the result is already computed, use it
        if start in self.memo:
            return self.memo[start]

        size = len(nums)
        remaining_length = size - start

        # If remaining length can be covered in one jump, return 1
        if remaining_length <= nums[start]:
            return 1

        # If current position is zero, can't move further
        if nums[start] == 0:
            return float('inf')

        jumps = float('inf')

        # Try every jump length from 1 to nums[start]
        for i in range(1, nums[start] + 1):
            temp = self.jump(nums, start + i)
            if temp != float('inf'):
                jumps = min(jumps, 1 + temp)

        self.memo[start] = jumps
        return jumps

Method 3 - Greedy Using BFS

The solution is based on a greedy approach where we track the maximum steps of the last jump:

For each position, we calculate the farthest point that can be reached.
The main idea is to keep track of the range of the current jump [curBegin, curEnd] and the farthest point curFarthest that all points in [curBegin, curEnd] can reach.
Once the current index reaches curEnd, trigger another jump, and set curEnd to curFarthest. Continue this process until we either reach the end of the array or determine that it’s impossible.

Approach

Initialize: Start with the first index. Track the current jump range [curBegin, curEnd] and the farthest index that all points in this range can reach (curFarthest).
Iterate: Traverse the array and for each index, update curFarthest.
Trigger Jumps: When the current index reaches curEnd, increment the jump count and set curEnd to curFarthest.
End Check: If curEnd reaches or exceeds the last index, return the number of jumps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public class Solution {
    public int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        
        int jumps = 0;
        int curEnd = 0;
        int curFarthest = 0;
        
        for (int i = 0; i < nums.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + nums[i]);
            
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
                if (curEnd >= nums.length - 1) {
                    break;
                }
            }
        }
        
        return jumps;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        
        jumps: int = 0
        cur_end: int = 0
        cur_farthest: int = 0
        
        for i in range(len(nums) - 1):
            cur_farthest = max(cur_farthest, i + nums[i]) 
            if i == cur_end:
                jumps += 1
                cur_end = cur_farthest
                if cur_end >= len(nums) - 1:
                    break
        
        return jumps

Complexity

⏰ Time complexity: O(n), where n is the length of the array.
🧺 Space complexity: O(1), as we use a constant amount of extra space.

Problem#

Examples#

Solution#

Method 1 - Recursion#

Code#

Complexity#

Method 2 - Using Top Down Dynamic Programming#

Code#

Method 3 - Greedy Using BFS#

Approach#

Code#

Complexity#

Problem

Examples

Solution

Method 1 - Recursion

Code

Complexity

Method 2 - Using Top Down Dynamic Programming

Code

Method 3 - Greedy Using BFS

Approach

Code

Complexity