Minimum Jumps

Given an array arr[] of non-negative integers. Each array element represents the maximum length of the jumps that can be made forward from that element. This means if arr[i] = x, then we can jump any distance y such that y ≤ x.
Find the minimum number of jumps to reach the end of the array starting from the first element. If an element is 0, then you cannot move through that element.
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.

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Constraints:
0 ≤ arr[i] ≤ 10⁵
2 ≤ arr.size() ≤ 10⁶

Approach 01:

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        int jumps = 0;
        int furthestReachable = INT_MIN;
        int currentEnd = 0;

        for (int i = 0; i < n; i++) {
            furthestReachable = max(furthestReachable, i + arr[i]);

            if (i == currentEnd) {
                currentEnd = furthestReachable;
                jumps++;

                if (currentEnd >= n - 1) {
                    return jumps;
                }
            }
        }
        return -1;
    }
};

from typing import List

class Solution:
    def minJumps(self, arr: List[int]) -> int:
        n = len(arr)
        jumps = 0
        furthestReachable = float('-inf')
        currentEnd = 0

        for i in range(n):
            furthestReachable = max(furthestReachable, i + arr[i])

            if i == currentEnd:
                currentEnd = furthestReachable
                jumps += 1

                if currentEnd >= n - 1:
                    return jumps

        return -1

Time Complexity

• Main Function minJumps:

  The function minJumps iterates over the array arr once using a single loop. For each element, it computes the furthest reachable index from the current position and updates the number of jumps required. Therefore, the time complexity is \( O(n) \), where n is the size of the input array arr.

Space Complexity

• Auxiliary Space:

  The space complexity is \( O(1) \) because the algorithm only uses a fixed amount of additional space (for variables like jumps, furthestReachable, and currentEnd), regardless of the size of the input array.