NUHMAN.com

Introduction

LeetCode 45: Jump Game II is a problem where you're tasked with finding the minimum number of jumps required to reach the last index of an array. Each element in the array represents the maximum number of indices you can jump forward from that position.

This problem can be solved optimally using a greedy algorithm, where we always try to extend our reachable range as far as possible with each jump, ensuring we minimize the number of jumps required.

Problem Statement

Given an array of non-negative integers nums, where each element represents the maximum number of steps you can jump forward from that position, return the minimum number of jumps to reach the last index.

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

Examples

go

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

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

go

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

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Approach: Greedy Algorithm

The core idea behind the greedy solution is to track the furthest we can reach at each step and try to minimize the number of jumps.

Steps:

1. Initialize variables:

• jumps: The number of jumps taken.
• current_end: The furthest index we can reach with the current number of jumps.
• farthest: The furthest index we can potentially reach in the next jump.

1. Iterate through the array:

• For each position in the array, update the farthest index you can reach. If you reach current_end, it means you need to make another jump to go further, so increment jumps and set current_end to farthest.

1. Stop when you can reach the last index.

Go Implementation

go

func jump(nums []int) int {
    n := len(nums)
    if n == 1 {
        return 0
    }

    jumps := 0
    current_end := 0
    farthest := 0

    for i := 0; i < n-1; i++ {
        farthest = max(farthest, i+nums[i])

        // If we have reached the farthest point for the current jump
        if i == current_end {
            jumps++
            current_end = farthest

            // If we can reach the last index
            if current_end >= n-1 {
                break
            }
        }
    }

    return jumps
}

// Helper function to find the maximum
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Example Walkthrough

Example 1:

go

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

1. Initialization:

• jumps = 0
• current_end = 0
• farthest = 0

1. Iteration:

• For i = 0, farthest = max(0, 0+2) = 2
• Since i == current_end (i.e., we have reached the farthest point for this jump), we increment jumps to 1 and update current_end = 2.
• For i = 1, farthest = max(2, 1+3) = 4
• Since i == current_end again, we increment jumps to 2 and update current_end = 4.

1. Final Output: We reached the last index, so the minimum number of jumps is 2.

Example 2:

go

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

1. Initialization:

• jumps = 0
• current_end = 0
• farthest = 0

1. Iteration:

• For i = 0, farthest = max(0, 0+2) = 2
• Since i == current_end, we increment jumps to 1 and update current_end = 2.
• For i = 1, farthest = max(2, 1+3) = 4
• Since i == current_end, we increment jumps to 2 and update current_end = 4.

1. Final Output: We reached the last index, so the minimum number of jumps is 2.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity: The algorithm iterates over the array exactly once, so the time complexity is O(n), where n is the length of the array nums.
• Space Complexity: The algorithm only uses a few variables (jumps, current_end, farthest), so the space complexity is O(1).

Edge Cases

• Single Element: If the array has only one element, no jumps are needed since we're already at the last index.
• Input: [0]
• Output: 0
• Maximum Jump at Each Step: If the array has large jumps at each position, we should still calculate the minimum number of jumps.
• Input: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
• Output: 1
• Smallest Array: If the array only contains two elements, it can always be solved in one jump if nums[0] is greater than or equal to 1.
• Input: [1, 2]
• Output: 1

Key Takeaways

• The greedy algorithm for solving Jump Game II optimizes the process by always extending the reachable range as much as possible with each jump.
• Tracking the farthest reachable index and updating the current_end ensures that we minimize the number of jumps.
• The problem can be solved in linear time and constant space, making it an efficient solution for large inputs.