Minimum number of jumps in Java

minimum number of jumps in java

Given an array of N integers arr[] where each element represents the maximum length of the jump 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.

Example 1:

Input:
N = 11 
arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} 
Output: 3

Solution :

The solution we are going to see is based on the greedy approach. We keep track of the current and farthest reachable indices and make a jump whenever we reach the farthest reachable index from the current position. We also handle cases where we can't move forward (i.e. the current element is 0) or we've reached the end of the array. The time complexity of this algorithm is O(n), where n is the length of the input array.

public class Solution {
    public static int minJumps(int[] arr) {
        if (arr.length <= 1) {
            return 0;
        }

        // If the first element is 0, then we can't move forward
        if (arr[0] == 0) {
            return -1;
        }

        // Initialize variables to keep track of the current and farthest reachable indices
        int currentReach = arr[0];
        int maxReach = arr[0];

        // Initialize variables to keep track of the number of jumps and the current position
        int jumps = 1;
        int i = 1;

        // Traverse the array, updating variables as necessary
        while (i < arr.length) {
            // If we've reached the end of the array, return the number of jumps
            if (i == arr.length - 1) {
                return jumps;
            }

            // Update the farthest reachable index
            maxReach = Math.max(maxReach, i + arr[i]);

            // If we've reached the farthest reachable index from the current position, make a jump
            if (i == currentReach) {
                jumps++;
                currentReach = maxReach;
            }

            // If we can't move forward (i.e. the current element is 0 and we're not at the end of the array), return -1
            if (i >= currentReach && arr[i] == 0) {
                return -1;
            }

            i++;
        }

        return -1;
    }
}