medium Jump Game II

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

public class Solution {

  public int jump(int[] nums) {
    int jumps = 0; // To count the number of jumps
    int currentEnd = 0; // To mark the end of the range for the current jump
    int farthest = 0; // To mark the farthest point that can be reached

    // Loop through the array
    for (int i = 0; i < nums.length - 1; i++) {
      farthest = Math.max(farthest, i + nums[i]); // Update the farthest point
      if (i == currentEnd) { // If reached the end of the current jump range
        jumps++; // Increment jump count
        currentEnd = farthest; // Update the end of the range to the farthest point
      }
    }

    return jumps; // Return the number of jumps
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test examples
    int[] example1 = { 2, 3, 2, 2, 1 };
    int[] example2 = { 1, 2, 3, 4, 5 };
    int[] example3 = { 2, 3, 1, 2, 4, 1 };

    // Print the results
    System.out.println(solution.jump(example1)); // Expected Output: 2
    System.out.println(solution.jump(example2)); // Expected Output: 3
    System.out.println(solution.jump(example3)); // Expected Output: 3
  }
}

Complexity Analysis

• Time Complexity: The algorithm runs in time, where n is the length of the array. This is because we iterate through the array once, and each operation inside the loop (like updating the farthest point) takes constant time.
• Space Complexity: The algorithm uses additional space since we are only using a few extra variables (jumps, currentEnd, and farthest) regardless of the input size.