45. Jump Game II - Detailed Explanation

Problem Statement

Description:
You are given an array of non-negative integers nums. Each element in the array represents your maximum jump length from 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.

Example 1:

• Input: nums = [2, 3, 1, 1, 4]
• Output: 2
• Explanation:
  • Jump 1: From index 0, jump 1 step to index 1 (or 2, but choosing index 1 is optimal here because it allows a jump to the end).
  • Jump 2: From index 1, jump 3 steps to index 4 (last index).

Example 2:

• Input: nums = [2, 1]
• Output: 1
• Explanation:
  • From index 0, jump directly to index 1.

Constraints:

• 1 ≤ nums.length ≤ 10⁴ (or more in some variations)
• 0 ≤ nums[i] ≤ 1000
• It is guaranteed that you can always reach the last index.

Hints

• Hint 1:
  Think about how far you can reach from each index. As you move along the array, keep track of the farthest index you can get to.

• Hint 2:
  At each step, consider the current range you can reach with the current number of jumps and determine the farthest point you can jump to in the next move.

• Hint 3:
  A greedy strategy works well here: while traversing the current jump range, update the farthest reachable index. When you pass the current range, you increment the jump counter and update the range to this farthest point.

Approach 1: Greedy Algorithm (Optimal)

Idea

The optimal greedy solution works by maintaining a current range (the farthest index reachable with the current number of jumps) and a farthest (the farthest index that can be reached by using one more jump within the current range).

Steps:

1. Initialize Variables:

   • jumps: count of jumps taken.
   • current_end: the end of the current jump range.
   • farthest: the farthest index reachable within the current range.

2. Iterate Through the Array:

   • For each index i in the array (except the last index), update farthest as max(farthest, i + nums[i]).
   • When you reach the end of the current range (i == current_end), you have finished exploring the current jump. Increment jumps and update current_end to farthest.
   • Continue until you reach or exceed the last index.

3. Return the Number of Jumps:
   After processing the array, the jumps variable holds the minimum number of jumps required.

Visual Walkthrough

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

• Initial:

  • jumps = 0, current_end = 0, farthest = 0.

• Iteration:

  • i = 0:

    • From index 0, you can jump up to index 0 + 2 = 2.
    • Update farthest = max(0, 2) = 2.
    • Since i equals current_end (0 == 0), increment jumps to 1 and set current_end = farthest (2).

  • i = 1:

    • From index 1, you can jump up to index 1 + 3 = 4.
    • Update farthest = max(2, 4) = 4.

  • i = 2:

    • From index 2, you can jump up to index 2 + 1 = 3.
    • farthest remains max(4, 3) = 4.
    • Now, i equals current_end (2 == 2) from the previous range, so increment jumps to 2 and update current_end to farthest (4).

• At this point, current_end (4) reaches the last index.

• Output: 2 jumps are needed.

Approach 2: Dynamic Programming (Less Optimal)

Idea

The dynamic programming approach calculates the minimum jumps needed to reach each index and builds up the solution.

Steps:

1. Initialize an Array dp:
   Create an array dp where dp[i] represents the minimum number of jumps required to reach index i. Initialize dp[0] to 0 and the rest to a large number (or infinity).

2. Update DP Array:
   For every index i, iterate through the indices reachable from i (from i+1 to min(i + nums[i], n-1)) and update dp[j] = min(dp[j], dp[i] + 1).

3. Result:
   The answer will be dp[n-1].

Discussion

• Pros:
  • It is straightforward to understand and implement.
• Cons:
  • The time complexity is O(n²) in the worst case, which is less efficient than the greedy approach for larger input sizes.

Code Implementation

Python Code (Greedy Approach)