Minimum number of jumps to reach end

Problem Statement

Given an array of non-negative integers where each element represents the maximum number of steps you can jump forward from that position, find the minimum number of jumps to reach the last index starting from the first index.

Example:

• Input: arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
• Output: 3 (Jump from 0→1, 1→4, 4→10)

Noob-Friendly Explanation

Imagine you're playing a board game where each square tells you the maximum number of steps you can jump forward. You start on the first square and want to reach the last square. You want to get there in the fewest jumps possible. For example, if a square says "3", you can jump 1, 2, or 3 squares ahead. What's the smartest way to hop to the end?

Approach 1: Brute Force

Intuition

From each position, try all possible jumps. Recursively find the minimum number of jumps to reach the end from each reachable position.

Algorithm

1. Start at index 0.
2. For each position, try jumping 1 to arr[i] steps forward.
3. Recursively find the minimum jumps from each landing position.
4. Return 1 + the minimum of all recursive results.

class Solution {
    public static int minJumpsBrute(int[] arr, int index) {
        int n = arr.length;

        // Reached or passed the end
        if (index >= n - 1) return 0;

        // Can't move from this position
        if (arr[index] == 0) return Integer.MAX_VALUE;

        int minJumps = Integer.MAX_VALUE;
        for (int jump = 1; jump <= arr[index] && index + jump < n; jump++) {
            int result = minJumpsBrute(arr, index + jump);
            if (result != Integer.MAX_VALUE) {
                minJumps = Math.min(minJumps, 1 + result);
            }
        }

        return minJumps;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        System.out.println(minJumpsBrute(arr, 0)); // Output: 3
    }
}

Complexity Analysis

• Time Complexity: O(n^n) - in the worst case, each position branches into many choices
• Space Complexity: O(n) - recursion stack depth

Approach 2: Optimal

Intuition

Use a greedy approach. At each step, track the farthest position we can reach. When we've used up the current jump's range, we must make another jump. This is like BFS on the positions — each "level" is one jump.

Algorithm

1. Track farthest (farthest reachable), currentEnd (end of current jump range), and jumps.
2. Iterate through the array. At each index, update farthest.
3. When we reach currentEnd, we must jump: increment jumps and set currentEnd = farthest.
4. Return jumps.

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

        int jumps = 0;
        int currentEnd = 0;  // End of range for current jump
        int farthest = 0;     // Farthest we can reach

        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + arr[i]);

            // We've reached the end of the current jump's range
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;

                // If we can already reach the end, stop
                if (currentEnd >= n - 1) break;
            }
        }

        return jumps;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        System.out.println(minJumps(arr)); // Output: 3
    }
}

Complexity Analysis

• Time Complexity: O(n) - single pass through the array
• Space Complexity: O(1) - only a few variables used