Leetcode 45. Jump Game II

 45. Jump Game II

Medium, Dynamic Programming

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

 

Example 1:

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:

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

 

Constraints:

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

The Jump Game II problem can be solved efficiently using a Greedy Algorithm. The goal is to determine the minimum number of jumps needed to reach the last index.

---

Approach:

1. Greedy Approach:
   • Track the farthest position that can be reached in the current jump.
   • Use a variable to count the current jumps.
   • At each step, if the current index matches the end of the current range of the jump, increment the jump count and update the range to the farthest position reached so far.

---

Steps:

1. Initialize Variables:

   • jumps: Counts the number of jumps required (start with 0).
   • current_end: Tracks the end of the current jump range.
   • farthest: Tracks the farthest index reachable within the current range.

2. Iterate Through the Array:

   • Update farthest for each index based on the jump capability from that index.
   • If the current index reaches current_end, it means the current jump ends, so increment the jump count and update current_end to farthest.

3. Stop Early:

   • Once the current_end reaches or exceeds the last index, return the number of jumps.

---

Implementation:

public class Solution {
    public int Jump(int[] nums) {
        int n = nums.Length;
        if (n == 1) return 0; // No jumps needed if there's only one element
        
        int jumps = 0, currentEnd = 0, farthest = 0;
        
        for (int i = 0; i < n - 1; i++) {
            // Update the farthest point reachable
            farthest = Math.Max(farthest, i + nums[i]);
            
            // If we reach the end of the current jump range
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // If we've reached or passed the last index, stop early
                if (currentEnd >= n - 1) break;
            }
        }
        
        return jumps;
    }
}

---

Explanation of Code:

1. Initialization:

   • jumps is initially 0 because no jumps have been made.
   • currentEnd is the range limit for the current jump.
   • farthest tracks the maximum reachable index.

2. Iterating Through nums:

   • Update farthest to be the maximum reachable index from the current position.
   • If i == currentEnd, it means the current jump has reached its range limit:
     • Increment the jump count (jumps++).
     • Update currentEnd to farthest.

3. Termination:

   • As soon as currentEnd reaches or exceeds n - 1, the loop ends early.

---

Complexity Analysis:

1. Time Complexity:

   • $O(n)$: Single traversal of the array.

2. Space Complexity:

   • $O(1)$: Only a few variables are used.

---

Examples:

Example 1:

• Input: nums = [2,3,1,1,4]
• Steps:
  1. Jump to index 1 (farthest: 4).
  2. Jump directly to the last index.
• Output: 2.

Example 2:

• Input: nums = [2,3,0,1,4]
• Steps:
  1. Jump to index 1 (farthest: 4).
  2. Jump directly to the last index.
• Output: 2.

This greedy algorithm ensures that the solution is efficient and handles large inputs within constraints.