Geeksforgeeks: Minimum Jumps

 

Minimum Jumps

Difficulty: Medium

You are given an array arr[] of non-negative numbers. Each number tells you the maximum number of steps you can jump forward from that position.

For example:

• If arr[i] = 3, you can jump 1 step, 2 steps, or 3 steps forward from position i.
• If arr[i] = 0, you cannot jump forward from that position.

Your task is to find the minimum number of jumps needed to move from the first position in the array to the last position.

Note:  Return -1 if you can't reach the end of the array.

Examples : 

Input: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
Output: 3 
Explanation: First jump from 1st element to 2nd element with value 3. From here we jump to 5th element with value 9, and from here we will jump to the last. 

Input: arr = [1, 4, 3, 2, 6, 7]
Output: 2 
Explanation: First we jump from the 1st to 2nd element and then jump to the last element.

Input: arr = [0, 10, 20]
Output: -1
Explanation: We cannot go anywhere from the 1st element.

Constraints:
2 ≤ arr.size() ≤ 106
0 ≤ arr[i] ≤ 105

Minimum Jumps Problem

The goal is to find the minimum number of jumps to reach the last index of an array, where each element of the array represents the maximum number of steps you can jump forward from that position.

Approach:

We can solve this problem efficiently using a greedy approach. The main idea is to keep track of the farthest we can reach with the current jump, and when that is exceeded, we make another jump.

Key Steps:

1. Track Current and Maximum Reach:

   • currentEnd: The farthest index you can reach with the current jump.
   • farthest: The farthest index you can reach so far with the current jump or upcoming jumps.

2. Greedy Jumping:

   • Iterate through the array, and for each element, update the farthest index.
   • When the farthest index exceeds or equals the end of the array, return the jump count.
   • If we have reached the currentEnd (i.e., the farthest we can go with the current jump), increment the jump counter and update currentEnd to farthest.

3. Edge Case:

   • If at any point, the current element is 0 and it blocks progress (i.e., no possible jump forward), return -1.

Code Implementation:

public class Solution {
    public int Jump(int[] arr) {
        int n = arr.Length;
        if (n <= 1) return 0;  // No jump needed if already at the end
        
        int jumps = 0;
        int farthest = 0;
        int currentEnd = 0;
        
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.Max(farthest, i + arr[i]);  // Update the farthest reachable index
            
            // If we've reached the end of the current jump, we must make another jump
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // If the current jump takes us to or beyond the end of the array, we return jumps
                if (currentEnd >= n - 1) return jumps;
            }
        }
        
        return -1;  // If we exit the loop without reaching the end, it's not possible to reach the end
    }
}

Explanation:

1. Initialization:

   • jumps: Tracks the number of jumps taken to reach the end.
   • farthest: Tracks the farthest index that can be reached from the current position.
   • currentEnd: Tracks the end of the current jump range.

2. Iterate through the array:

   • For each index i, calculate the farthest index that can be reached from index i (farthest = Math.Max(farthest, i + arr[i])).
   • If i reaches currentEnd, it means we have finished a jump and need to move to the next jump range. Update jumps and currentEnd.
   • If currentEnd reaches or exceeds n-1 (the last index), we return the number of jumps.

3. Edge Case Handling:

   • If arr[0] == 0, it's not possible to move anywhere, so return -1.

Time Complexity:

• Time Complexity: $O(n)$, where n is the length of the input array. We are iterating through the array once, and all operations within the loop are constant time.
• Space Complexity: $O(1)$, as we only use a few extra variables for tracking the jumps and indices.

Example Walkthrough:

Example 1:

• Input: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
• Steps:
  1. Start at index 0, jump to index 1 (farthest = 3).
  2. From index 1, jump to index 5 (farthest = 9).
  3. From index 5, jump to index 10 (end).
• Output: 3

Example 2:

• Input: arr[] = [1, 4, 3, 2, 6, 7]
• Steps:
  1. Start at index 0, jump to index 1 (farthest = 5).
  2. From index 1, jump to index 5 (end).
• Output: 2

Example 3:

• Input: arr[] = [0, 10, 20]
• Steps:
  • At index 0, the element is 0, so we cannot jump anywhere.
• Output: -1

Conclusion:

The greedy approach is optimal for this problem. By keeping track of the farthest index we can reach with each jump and incrementing jumps when necessary, we can solve this problem in linear time $O(n)$.