Minimum Jumps to Reach End

function minJumpsLeftToRight(arr) {
    const n = arr.length;
    if (n === 0 || arr[0] === 0) return -1;
 
    const jumps = new Array(n).fill(Infinity);
    jumps[0] = 0; // Base case: 0 jumps to reach index 0
 
    // Fill jumps array from left to right
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            // If i is reachable from j, and it's a better jump count
            if (i <= j + arr[j] && jumps[j] !== Infinity) {
                jumps[i] = Math.min(jumps[i], jumps[j] + 1);
                break; // Optional: since we seek min jumps and move left to right, we can't find a better path here
            }
        }
    }
 
    return jumps[n - 1] === Infinity ? -1 : jumps[n - 1];
}

function minJumpsRightToLeft(arr) {
    const n = arr.length;
    if (n === 0 || arr[0] === 0) return -1;
 
    const jumps = new Array(n).fill(Infinity);
    jumps[n - 1] = 0; // Base case: 0 jumps to reach end from end
 
    // Fill jumps array from right to left
    for (let i = n - 2; i >= 0; i--) {
        if (arr[i] === 0) {
            jumps[i] = Infinity;
        } else if (i + arr[i] >= n - 1) {
            jumps[i] = 1; // Can reach end in a single jump
        } else {
            // Find minimum jumps from reachable indexes ahead
            let min = Infinity;
            for (let j = i + 1; j < n && j <= i + arr[i]; j++) {
                if (jumps[j] < min) {
                    min = jumps[j];
                }
            }
            jumps[i] = (min !== Infinity) ? min + 1 : Infinity;
        }
    }
 
    return jumps[0] === Infinity ? -1 : jumps[0];
}

function minJumpsGreedy(arr) {
    const n = arr.length;
    if (n <= 1) return 0;
    if (arr[0] === 0) return -1;
 
    // Stores the maximum index reachable from the current state
    let maxReach = arr[0];
 
    // Stores the number of steps we can still take
    let steps = arr[0];
 
    // Stores the number of jumps made
    let jumps = 1;
 
    // Start traversing the array
    for (let i = 1; i < n - 1; i++) {
        // Update maxReach
        maxReach = Math.max(maxReach, i + arr[i]);
 
        // Use a step to move to the current index
        steps--;
 
        // If no more steps are left
        if (steps === 0) {
            // We must have made a jump
            jumps++;
 
            // Check if a future step is possible
            if (i >= maxReach) return -1;
 
            // Re-initialize the steps to the amount of steps to reach maxReach from i
            steps = maxReach - i;
        }
    }
 
    return jumps;
}
 
// Driver code
const arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
console.log("Minimum jumps to reach end:", minJumpsGreedy(arr));
// Output: Minimum jumps to reach end: 3