Find Minimum Jumps to Reach the End of an Array

Title: Find Minimum Jumps to Reach the End of an Array

Minimum jumps to reach the end of an array is a classic array and greedy algorithm problem that shows up constantly in coding interviews. Given an array where each element tells you the maximum number of steps you can take forward from that position, the task is to find the smallest number of jumps needed to land on the last index.

In this guide, you’ll learn how to think about the problem as a sequence of expanding reachable ranges, walk through a greedy O(n) solution step by step, and see how the algorithm handles tricky inputs like a 0 that blocks all further progress. By the end you’ll be able to explain, trace, and defend this solution confidently in an interview.

Understanding the Problem

You are given an array of non-negative integers nums, where nums[i] represents the maximum number of positions you can jump forward from index i. Starting at index 0, you want to reach index nums.length - 1 using as few jumps as possible.

The problem is often stated with a guarantee that the last index is always reachable, but a solid solution should still detect and report the case where it is not, for example when the array contains a 0 that strands you before the end. In that case the method returns -1.

Approach to Solve the Problem

1. If the array has only one element, you are already at the last index, so 0 jumps are needed.
2. If nums[0] is 0 and the array has more than one element, the last index can never be reached, so return -1 immediately.
3. Track three running values: jumps (the number of jumps taken so far), maxReach (the farthest index reachable using the jumps taken so far), and stepsLeftInCurrentJump (how many more indices you can visit before you must commit to the next jump).
4. Walk the array from index 1 onward. At each index, update maxReach to the farther of its current value and i + nums[i].
5. Decrement stepsLeftInCurrentJump. When it reaches 0, the current jump’s range is exhausted, so increment jumps and reset stepsLeftInCurrentJump to maxReach - i.
6. Immediately after incrementing jumps, check whether the pointer is stuck: if i >= maxReach, no further progress is possible, so return -1.
7. Stop as soon as the loop reaches the last index and return the accumulated jumps count.

Java Program

public class MinimumJumps {

    public static int minJumps(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return 0;
        }
        if (nums[0] == 0) {
            return -1;
        }

        int jumps = 1;
        int maxReach = nums[0];
        int stepsLeftInCurrentJump = nums[0];

        for (int i = 1; i < n; i++) {
            if (i == n - 1) {
                return jumps;
            }

            maxReach = Math.max(maxReach, i + nums[i]);
            stepsLeftInCurrentJump--;

            if (stepsLeftInCurrentJump == 0) {
                jumps++;
                if (i >= maxReach) {
                    return -1;
                }
                stepsLeftInCurrentJump = maxReach - i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        int result = minJumps(nums);
        System.out.println("Minimum jumps needed: " + result);
    }
}

Explanation of the Program

• jumps starts at 1 because, once nums[0] > 0 is confirmed, the first jump is already committed to.
• maxReach is only ever updated with Math.max, so it never shrinks. It represents the farthest index reachable using the jumps counted so far.
• stepsLeftInCurrentJump counts down the remaining indices you can visit before the current jump’s range runs out.
• When stepsLeftInCurrentJump hits 0, the loop commits to the next jump: it increments jumps and resets the countdown to maxReach - i.
• The loop returns early the moment i equals the last index, so the algorithm never processes positions past the point where the answer is already known.
• The i >= maxReach check right after incrementing jumps detects an unreachable last index and returns -1 instead of looping forever or reporting a wrong count.

Step-by-Step Trace

For nums = {3, 1, 1, 1, 1, 1}, the target output is 3 jumps. The table below traces indices 1 through 4; at index 5 the loop recognizes it has reached the last index and returns immediately.

At the end of each iteration, maxReach holds the farthest index reachable using the jumps counted so far, and jumps increases only once stepsLeftInCurrentJump for the active jump has been fully spent.

Examples

Example 1: A Reachable Array

The first jump from index 0 can reach as far as index 2, and from there index 2 can reach all the way to the last index, so only two jumps are needed.

int[] nums = {2, 3, 1, 1, 4};
System.out.println(minJumps(nums));
// Output: 2

Example 2: Every Step Is Forced

When every element is 1, each jump can only advance one position, so the number of jumps equals the number of steps between the first and last index.

int[] nums = {1, 1, 1, 1, 1};
System.out.println(minJumps(nums));
// Output: 4

Example 3: An Unreachable Last Index

Index 3 holds a 0, and no earlier jump can skip over it to land past it, so the last index can never be reached.

int[] nums = {3, 2, 1, 0, 4};
System.out.println(minJumps(nums));
// Output: -1

Common Mistakes to Avoid

These are the slip-ups that most often turn a correct-looking greedy jump solution into a wrong answer or an infinite loop.

• Starting jumps at 0 – the method undercounts by one and returns one fewer jump than actually required, because the first jump from index 0 was never counted. Initialize jumps = 1 as soon as nums[0] > 0 is confirmed.
• Skipping the stuck check – the loop keeps counting jumps even after a block of zeros has trapped the pointer, so the method returns a positive jump count for an input that should return -1. Add the i >= maxReach guard right after incrementing jumps.
• Recomputing maxReach from scratch – writing maxReach = i + nums[i] instead of maxReach = Math.max(maxReach, i + nums[i]) throws away a farther reach discovered at an earlier index, so later jumps look shorter than they really are.
• Forgetting the single-element shortcut – checking nums[0] == 0 before checking n <= 1 returns -1 for new int[]{0}, even though that array is already at its last index with zero jumps needed.
• Mixing up the two counters - accidentally returning stepsLeftInCurrentJump instead of jumps reports how many positions remain in the current jump, not how many jumps have happened, which is wildly wrong on longer arrays.

Edge Cases to Test

Run through these input shapes before calling the solution finished; interviewers specifically look for this habit.

• Single-element array
• Array starting with 0 and length greater than 1
• Two-element array
• A 0 embedded mid-array that blocks progress
• All elements equal to 1
• A jump length large enough to reach the last index directly from index 0
• Integer.MAX_VALUE as a jump value

Additional Considerations

The greedy approach runs in O(n) time with O(1) extra space, because it makes a single pass over the array and only tracks a handful of counters. A dynamic programming alternative, where dp[i] stores the minimum jumps to reach index i, also solves the problem but costs O(n^2) time in its straightforward form and O(n) extra space for the dp array, so prefer the greedy version whenever a single optimal answer, rather than all intermediate answers, is needed.

The Integer.MAX_VALUE edge case matters because computing i + nums[i] on a very large jump value can overflow a 32-bit int and wrap around to a negative number, which would wrongly shrink maxReach. If the input might realistically contain such extreme values, clamp the sum or compute it using long arithmetic before assigning it back.

Interview Follow-up Questions

Once you can explain the base solution, expect an interviewer to push further with questions like these.

• What if you also need the actual sequence of indices visited, not just the jump count? - track a predecessor index alongside each update to maxReach, then walk it backward from the last index once the jump count is known.
• What if negative jump lengths are allowed, representing a move backward? - the greedy approach no longer guarantees optimality, so switch to a BFS or Dijkstra-style shortest-path search over the index graph instead.
• What if the solution must use only a couple of counters and no auxiliary array, even in the worst case? - the greedy version already satisfies this; verify that any DP-style rewrite is not accidentally reintroduced.
• What if the array arrives as a stream and you cannot look ahead past the current index? - maxReach can only be updated from indices already seen, so a single pass can still track it, but you cannot peek ahead to confirm the last index is reachable until the stream ends.
• What if the array has billions of elements and does not fit in memory? - process it in chunks, carrying forward only jumps, maxReach, and stepsLeftInCurrentJump between chunks, since the greedy algorithm's state is O(1) and never needs random access to earlier elements.

Conclusion

The minimum jumps problem is a great example of how tracking the right running state turns an apparently exponential search into a single O(n) pass. Once you internalize maxReach as the frontier of what the current jump count can reach, the greedy update falls out naturally.

Try adapting the code to return the chosen indices instead of just the count, or to handle an array that is guaranteed unreachable, to make sure the stuck-detection logic is second nature before your next interview. You can learn more about Java array algorithms in our Arrays category.