Minimum no. of Jumps to reach end of an array

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 required to reach the end of the array (last index) starting from the first index.

Example:

• Input: [2, 3, 1, 1, 4]
• Output: 2
• Explanation: Jump from index 0 to 1 (1 step), then from index 1 to 4 (1 step). Minimum jumps = 2.

Approach 1: Dynamic Programming (Brute Force)

Intuition

For each position, calculate the minimum jumps needed to reach it from the start. For position i, check all positions j (0 to i-1) from which we can reach i.

Algorithm

1. Create dp array where dp[i] = minimum jumps to reach index i
2. Initialize dp[0] = 0, all others to infinity
3. For each position i, check all j < i where j + arr[j] >= i
4. dp[i] = min(dp[i], dp[j] + 1)

import java.util.Arrays;

public class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0;
        if (arr[0] == 0) return -1;
        
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Can we reach i from j?
                if (j + arr[j] >= i && dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Two nested loops
• Space Complexity: O(n) - DP array

Approach 2: Greedy (Optimal)

Intuition

Think of it as BFS levels. Each "level" represents positions reachable with the same number of jumps. We greedily find the farthest position we can reach in each level.

Algorithm

1. Track jumps (number of jumps made), currentEnd (end of current jump range), farthest (farthest position reachable)
2. For each position, update farthest
3. When we reach currentEnd, we must make a jump - increment jumps and set currentEnd = farthest

public class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0;
        if (arr[0] == 0) return -1;
        
        int jumps = 0;
        int currentEnd = 0;  // End of current jump range
        int farthest = 0;    // Farthest position reachable
        
        for (int i = 0; i < n - 1; i++) {
            // Update farthest position reachable from current position
            farthest = Math.max(farthest, i + arr[i]);
            
            // If we've reached the end of current jump range
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                
                // If we can already reach or exceed the last index
                if (currentEnd >= n - 1) {
                    break;
                }
            }
        }
        
        return currentEnd >= n - 1 ? jumps : -1;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only three variables

Approach 3: BFS (Alternative Perspective)

Intuition

Treat this as a graph where each index connects to all reachable indices. BFS gives the shortest path.

Complexity Analysis

• Time Complexity: O(n²) - Worst case, each position adds many to queue
• Space Complexity: O(n) - Queue and visited array

Edge Cases

Key Takeaways

1. Greedy approach works because we always want to maximize reach at each step
2. Think of it as BFS levels - each level = positions reachable with same jumps
3. The key variables: currentEnd (boundary of current level) and farthest (max reach)
4. Time complexity reduces from O(n²) to O(n) with greedy
5. Similar problems: Jump Game I (can reach end?), Jump Game III (bi-directional jumps)
6. The greedy insight: we don't care WHERE we jump, just HOW FAR we can go