Minimum Jumps

Time: O(n)

Space: O(1)

Intuition

Greedy BFS: at each step, track the farthest reachable position (currentEnd) and the farthest position reachable in the next step (farthestReach). When we reach currentEnd, we must take a jump; increment jumps and update currentEnd to farthestReach.

Algorithm

1jumps=0, currentEnd=0, farthest=0.
2For i from 0 to nâˆ’2: farthest = max(farthest, i+arr[i]).
3If i == currentEnd: jumps++. currentEnd=farthest. If currentEnd >= n-1: break.
4Return jumps if reachable, else -1.

Example Walkthrough

Input: arr = [2,3,1,1,4]

1.i=0: farthest=2. currentEnd=0 â†’ jump, currentEnd=2, jumps=1.
2.i=1: farthest=4. i=2: farthest=4. currentEnd=2 â†’ jump, currentEnd=4â‰¥4, jumps=2. Break.

Output: 2

Common Pitfalls

•Iterate only to nâˆ’2 (not nâˆ’1) â€” you don't need a jump from the last position.

Minimum Jumps.java

Java

// Approach: Greedy BFS. Track current range end and farthest reachable. Each full range traversal = one jump.
// Time: O(n) Space: O(1)
class Solution {
    static int minJumps(int[] arr) {
        int n = arr.length;
        if (n == 0 || arr[0] == 0)
            return -1;

        if (n == 1)
            return 0;

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

            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }

            if (currentEnd >= n - 1)
                return jumps;
        }

        return -1;
    }
}

Was this solution helpful?