Problem Statement

You are given an array nums containing n integers, where nums[i] represents the maximum length of a forward jump you can make from index i. You are initially positioned at nums[0].

Return the minimum number of jumps needed to reach from the start to the end of the array.

Examples

Example 1:

• Input: nums = [2, 3, 2, 2, 1]
• Expected Output: 2
• Justification: Start at index 0 and jump to index 1 (jump size 1). Then, jump from index 1 to the end (jump size 3).

Example 2:

• Input: nums = [1, 2, 3, 4, 5]
• Expected Output: 3
• Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 3 (jump size 2). Finally, jump to the end (jump size 2).

Example 3:

• Input: nums = [2, 3, 1, 2, 4, 1]
• Expected Output: 3
• Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 4 (jump size 2). Finally, jump to the end (jump size 1).

Constraints:

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

Solution

To solve this problem, we need to keep track of the farthest point we can reach with each jump and count how many jumps we need. The strategy is to iterate through the array while updating the farthest point we can reach. Whenever we reach the end of the current jump range, we increment our jump count and update the current jump range to the farthest point we can reach. This method ensures that we use the fewest jumps possible to get to the end.

This approach works effectively because it uses a greedy algorithm to always make the optimal choice at each step. By focusing on the farthest reachable point, we minimize the number of jumps needed.

Step-by-Step Algorithm

1. Initialize Variables:

   • Create a variable jumps and set it to 0. This will count the number of jumps needed.
   • Create a variable currentEnd and set it to 0. This will mark the end of the range for the current jump.
   • Create a variable farthest and set it to 0. This will track the farthest point that can be reached.

2. Loop Through the Array:

   • Iterate through the array from the first element to the second-to-last element (from index 0 to n-2):
     • Update farthest to be the maximum of farthest and the current index plus the jump length at that index (farthest = max(farthest, i + nums[i])).
     • If the current index is equal to currentEnd:
       • Increment the jumps count (jumps++).
       • Update currentEnd to be farthest (currentEnd = farthest).

3. Return Result:

   • After the loop ends, return the value of jumps as the result.

Algorithm Walkthrough

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

Initialization:

• jumps = 0
• currentEnd = 0
• farthest = 0

Iteration 1:

• Index i = 0
  • farthest = max(0, 0 + 2) = 2
  • Since i == currentEnd (0 == 0):
    • jumps++ (jumps = 1)
    • currentEnd = farthest (currentEnd = 2)

Iteration 2:

• Index i = 1
  • farthest = max(2, 1 + 3) = 4
  • i != currentEnd (1 != 2), so do nothing

Iteration 3:

• Index i = 2
  • farthest = max(4, 2 + 1) = 4
  • Since i == currentEnd (2 == 2):
    • jumps++ (jumps = 2)
    • currentEnd = farthest (currentEnd = 4)

Iteration 4:

• Index i = 3
  • farthest = max(4, 3 + 2) = 5
  • i != currentEnd (3 != 4), so do nothing

Iteration 5:

• Index i = 4
  • farthest = max(5, 4 + 4) = 8
  • Since i == currentEnd (4 == 4):
    • jumps++ (jumps = 3)
    • currentEnd = farthest (currentEnd = 8)

Return Result:

• Return jumps which is 3.

Code