Minimum number of jumps to reach end using Java

This Java code calculates the minimum jumps needed to traverse an array, where each element represents the maximum jump distance from that position. Let's explore the algorithm and code step-by-step. The goal is to find the fewest jumps required to reach the array's end, starting from index 0. If the end is unreachable, the function returns -1.

Problem Definition:

Given an array arr[], where each element arr[i] indicates the maximum number of steps you can take forward from that position, determine the minimum number of jumps to reach the last index.

Algorithm:

The algorithm employs a greedy approach, iterating through the array and tracking the farthest reachable index (maxReach) at each step. It maintains a jumps counter and steps to track progress within each jump.

1. Initialization:

   • jumps: Counts the total number of jumps. Initialized to 0.
   • maxReach: The farthest index reachable from the current position. Initialized to arr[0].
   • steps: The number of steps remaining within the current jump. Initialized to arr[0].

2. Iteration:

   • The code iterates through the array.
   • For each element arr[i]:
     • Update maxReach to the maximum of maxReach and i arr[i] (the farthest reachable index from the current position).
     • Decrement steps (we've taken one step).
     • If steps becomes 0, it means we've exhausted the current jump's steps. Therefore:
       • Increment jumps.
       • If maxReach is less than or equal to i, it means we're stuck and can't reach further. Return -1.
       • Reset steps to maxReach - i (the remaining steps in the next jump).

3. Termination:

   • If the loop completes without returning -1, it means the end is reachable. The function returns jumps.

Java Code:

public class MinJumpsToEnd {
    public static int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0; // Already at the end or empty array

        int jumps = 0;
        int maxReach = arr[0];
        int steps = arr[0];

        for (int i = 1; i < n; i++) {
            maxReach = Math.max(maxReach, i + arr[i]); // Update maxReach
            steps--; // Decrement steps

            if (steps == 0) { // Jump needed
                jumps++;
                if (maxReach <= i) return -1; // Unreachable
                steps = maxReach - i; // Reset steps for next jump
            }
            if (i == n-1) return jumps; // Reached the end

        }
        return jumps;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 1, 2, 4, 2, 0, 1, 1};
        System.out.println("Minimum jumps required: " + minJumps(arr)); // Output: 4
    }
}

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the array. The code iterates through the array once.
• Space Complexity: O(1), as the algorithm uses a constant amount of extra space.

This improved explanation and code provide a clearer understanding of the algorithm and its implementation. The added comments enhance readability and the edge case handling (empty or single-element array) makes the code more robust.

The above is the detailed content of Minimum number of jumps to reach end using Java. For more information, please follow other related articles on the PHP Chinese website!