Minimum Number of Jumps to Reach End of an Array

Given an array where every element is the maximum forward jump distance from that position, find the fewest jumps needed to reach the last index.

The problem sounds simple. It is not trivial to solve optimally. The naive approach tries every reachable index at each step and backtracks, giving exponential time. The DP approach brings it down to O(n²). The greedy approach brings it down further to O(n) with O(1) space. Placement coding rounds at TCS NQT and Infosys InfyTQ both use this problem because it has three distinct solution levels and a follow-up question that separates candidates who understand what they wrote from candidates who memorised a template.

The Problem and Worked Examples

You start at index 0. Each element arr[i] is the maximum number of positions you can jump forward from index i. You can land anywhere from i + 1 to i + arr[i]. You want to reach index n - 1 in the fewest jumps.

If no path to the end exists, return -1.

Two examples, verified from first principles:

Example 1: Array [2, 3, 1, 1, 4], n=5

Greedy trace (variables: jumps, currentEnd, farthest; all start at 0):

• i=0: farthest = max(0, 0+2) = 2. i equals currentEnd, so jumps=1, currentEnd=2. Not done yet.
• i=1: farthest = max(2, 1+3) = 4.
• i=2: farthest = max(4, 2+1) = 4. i equals currentEnd, so jumps=2, currentEnd=4. Index 4 equals n-1. Return 2.

Answer: 2 jumps. Path: index 0 (jump to index 1) then index 1 (jump to index 4).

Example 2: Array [5, 5, 0, 4, 1, 4, 5, 5, 3, 2], n=10

• i=0: farthest = max(0, 0+5) = 5. i equals currentEnd, so jumps=1, currentEnd=5.
• i=1: farthest = max(5, 1+5) = 6.
• i=2: farthest = max(6, 2+0) = 6.
• i=3: farthest = max(6, 3+4) = 7.
• i=4: farthest = max(7, 4+1) = 7.
• i=5: farthest = max(7, 5+4) = 9. i equals currentEnd, so jumps=2, currentEnd=9. Index 9 equals n-1. Return 2.

Answer: 2 jumps. Path: index 0 (jump to index 5, value 4) then index 5 (jump to index 9, end).

Example 3 (impossible): Array [1, 0, 1], n=3

• i=0: farthest = 1. i equals currentEnd, so jumps=1, currentEnd=1.
• i=1: farthest = max(1, 1+0) = 1. i equals currentEnd, and farthest has not advanced past currentEnd. Return -1.

Answer: -1. The zero at index 1 blocks every path.

The Greedy Approach

The greedy algorithm for minimum jumps works by tracking two boundaries at a time: currentEnd marks the last index reachable with the jumps made so far, and farthest marks the furthest index reachable if you make one more jump from anywhere within currentEnd.

As you scan from left to right, you keep updating farthest. When your index reaches currentEnd, you commit to a new jump: jumps increments, and currentEnd advances to farthest. You do not need to decide which specific index to jump to, only when a jump is necessary.

The algorithm works because the jump count never increases unnecessarily. Any time you advance currentEnd, you are taking the single best possible jump from the current window. Skipping a jump when you could advance would only shrink the next window.

The key insight: you never need to revisit an index. Once i passes currentEnd, the next window covers it. One left-to-right pass suffices.

Greedy algorithm outline

• Step 1: If the array has one element, return 0 (already at the end).
• Step 2: If arr[0] equals 0, return -1 (cannot leave start).
• Step 3: Set jumps = 0, currentEnd = 0, farthest = 0.
• Step 4: Loop i from 0 to n - 2 (inclusive):
  • Update farthest = max(farthest, i + arr[i]).
  • If i equals currentEnd: increment jumps, set currentEnd = farthest. If currentEnd >= n - 1, return jumps. If farthest <= i, return -1.
• Step 5: Return jumps.

This runs in O(n) time and O(1) space.

The DP Approach

The DP approach builds a table dp where dp[j] is the minimum jumps needed to reach index j.

• dp[0] = 0 (you start here, zero jumps needed).
• For every index j from 1 to n-1, scan every earlier index i where i + arr[i] >= j. Set dp[j] = min(dp[j], dp[i] + 1).

DP trace for [2, 3, 1, 1, 4] (n=5):

• dp[0] = 0
• dp[1]: i=0, arr[0]=2, 0+2=2 >= 1. dp[1] = dp[0]+1 = 1.
• dp[2]: i=0, 0+2=2 >= 2. dp[2] = 1. i=1, 1+3=4 >= 2 but dp[1]+1=2 > 1. Stay at 1.
• dp[3]: i=0, 0+2=2 >= 3? No. i=1, 1+3=4 >= 3. dp[3] = dp[1]+1 = 2. i=2, 2+1=3 >= 3. dp[3] = min(2, dp[2]+1) = 2.
• dp[4]: i=0, 2 >= 4? No. i=1, 4 >= 4. dp[4] = dp[1]+1 = 2. i=2, 3 >= 4? No. i=3, 3+1=4 >= 4. dp[4] = min(2, dp[3]+1=3) = 2.

Answer: dp[4] = 2. Matches the greedy result.

The DP approach is O(n²) time and O(n) space. It is slower than greedy but useful in interviews where the interviewer asks you to show every sub-problem value on a whiteboard. The dp table also makes path reconstruction straightforward: trace back from dp[n-1] to find the actual indices in the optimal path.

Programs in C, Python, and Java

All three programs below read array size, then elements, and print the minimum jump count or -1.

C — greedy, O(n)

#include <stdio.h>

int minJumps(int arr[], int n) {
    if (n <= 1) return 0;
    if (arr[0] == 0) return -1;

    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < n - 1; i++) {
        if (i + arr[i] > farthest)
            farthest = i + arr[i];
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
            if (currentEnd >= n - 1) return jumps;
            if (farthest <= i) return -1;
        }
    }
    return jumps;
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
    printf("%d\n", minJumps(arr, n));
    return 0;
}

C programs for array problems follow the same read-then-process pattern across most Tier-2 college lab sheets and placement coding rounds. The C coding questions in placement rounds article covers the other array problems that appear alongside this one.

Python — greedy, O(n)

def min_jumps(arr):
    n = len(arr)
    if n <= 1:
        return 0
    if arr[0] == 0:
        return -1

    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(n - 1):
        farthest = max(farthest, i + arr[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= n - 1:
                return jumps
            if farthest <= i:
                return -1
    return jumps

n = int(input())
arr = list(map(int, input().split()))
print(min_jumps(arr))

Java — greedy, O(n)

import java.util.Scanner;

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

        int jumps = 0, currentEnd = 0, farthest = 0;
        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + arr[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                if (currentEnd >= n - 1) return jumps;
                if (farthest <= i) return -1;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        System.out.println(minJumps(arr));
    }
}

TCS NQT, Infosys InfyTQ, and AMCAT coding sections all accept C, C++, Java, and Python. Use whichever you can write from memory without syntax errors under time pressure.

Java — DP approach, O(n²)

For completeness, and for interviews where you are asked to show the dp table:

import java.util.Arrays;
import java.util.Scanner;

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

        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++) {
                if (dp[j] != Integer.MAX_VALUE && j + arr[j] >= i) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1] == Integer.MAX_VALUE ? -1 : dp[n - 1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        System.out.println(minJumpsDP(arr));
    }
}

The DP solution initialises every dp[i] to Integer.MAX_VALUE and reduces it as reachable paths are discovered. If dp[n-1] stays at MAX_VALUE after the full nested loop, no path exists and the function returns -1.

Complexity, Edge Cases, and Placement Context

Complexity table

Approach	Time	Space	Notes
Greedy	O(n)	O(1)	Single pass, three variables
DP	O(n²)	O(n)	Full dp table; easy to trace
Naive recursion	O(2^n)	O(n) stack	Do not use in interviews

Edge cases that trip up first-time solvers

• All ones: [1, 1, 1, 1] requires n-1 jumps. The greedy trace advances currentEnd by 1 at every step, so jumps counts up to 3 for a 4-element array.
• First element reaches the end directly: [5, 0, 0, 0] returns 1. The greedy trace fires i==currentEnd at i=0, increments jumps, sets currentEnd=5, which is >= n-1 = 3. Return 1.
• Zero at position blocking all paths: [2, 0, 0, 1] returns -1. From index 0 you can reach 1 or 2; both are 0. farthest stops at 2 when currentEnd is 2, and farthest <= i triggers the -1 return.
• Single-element array: return 0 immediately.

Pascal’s triangle in placement coding rounds is another problem where the nested-loop DP pattern appears. The dp table for minimum jumps and the binomial coefficient table share the same O(n²) fill pattern, which is worth recognising across problem types.

Where this appears in placement coding

The minimum jumps problem tests three things at once:

• Whether you can spot the greedy structure (most candidates default to DP or recursion first)
• Whether your loop bounds are correct (i < n - 1, not i < n, to avoid reading arr[n-1] as a jump)
• Whether you handle the -1 case explicitly

The GeeksforGeeks minimum jumps article documents several additional variants, including one where each jump costs a toll, which interviewers use as a follow-up once you have solved the base problem.

A common interview follow-up: “Now print the actual path of indices.” The greedy algorithm as written does not reconstruct the path. The DP approach does: once the dp table is filled, start from dp[n-1] and scan backwards for an index i where i + arr[i] >= n - 1 and dp[i] == dp[n-1] - 1. That index was the last jump. Repeat for each step.

The greedy solution makes one locally optimal decision per step and, globally, produces the minimum jump count without any backtracking. That relationship between local optimality and global correctness is what makes a problem “greedy-solvable” in the formal sense. The same provability structure appears in how autoregressive language models select tokens: each generation step picks the locally highest-probability token, and whether that produces the globally best output depends on the problem structure. If you want to probe where greedy token selection breaks down and when sampling or beam search does better, TinkerLLM at ₹299 lets you run those experiments on real models without needing GPU access or a research environment.