Jump Game - Minimum Jumps to Reach End

Last Updated : 3 Apr, 2026

Given an array arr[] of non-negative integers, where each element represents the maximum number of steps you can jump forward from that index, determine the minimum number of jumps required to reach the last index starting from the first index. If it is not possible to reach the end, return -1.

Examples: 

Input: arr[] = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
Output: 3
Explanation: First jump from 1st element to 2nd element with value 3. From here we jump to 5th element with value 9, and from here we will jump to the last.

Input: arr []= [1, 4, 3, 2, 6, 7]
Output: 2
Explanation: First we jump from the 1st to 2nd element and then jump to the last element.

Input: arr[] = [0, 10, 20]
Output: -1
Explanation: We cannot go anywhere from the 1st element.

Try it on GfG Practice
redirect icon

Table of Content

[Naive] Using Recursion - O(n^n) Time and O(n) Space

Recursively try all possible jumps from each index. From position i, we can jump to any index between i + 1 and i + arr[i], and for each of these, we compute the minimum jumps needed to reach the end. then take the minimum among those and add 1 for the current jump.
Basically minJumps(i) = 1 + min(minJumps(k)) for all valid k reachable from i.

C++ 
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Returns minimum jumps needed from index i to reach end
int minJumpsRecur(int i, vector<int> &arr) {
    if (i >= arr.size() - 1)
        return 0;

    int ans = INT_MAX;

    // Try all reachable positions from i
    for (int j = i + 1; j <= i + arr[i]; j++) {
        int val = minJumpsRecur(j, arr);
        if (val != INT_MAX)
            ans = min(ans, 1 + val);
    }

    return ans;
}

int minJumps(vector<int>& arr) {
    int ans = minJumpsRecur(0, arr);
    return (ans == INT_MAX) ? -1 : ans; 
}

int main() {
    vector<int> arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    cout << minJumps(arr);
    return 0;
}
Java 
import java.util.List;
import java.util.Arrays;

class GFG {

    // Returns minimum jumps needed from index i to reach end
    static int minJumpsRecur(int i, List<Integer> arr) {
        if (i >= arr.size() - 1)
            return 0;

        int ans = Integer.MAX_VALUE;

        // Try all reachable positions from i
        for (int j = i + 1; j <= i + arr.get(i) && j < arr.size(); j++) {
            int val = minJumpsRecur(j, arr);
            if (val != Integer.MAX_VALUE)
                ans = Math.min(ans, 1 + val);
        }

        return ans;
    }

    static int minJumps(List<Integer> arr) {
        int ans = minJumpsRecur(0, arr);
        return (ans == Integer.MAX_VALUE) ? -1 : ans; 
    }

    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9);
        System.out.println(minJumps(arr));
    }
}
Python 
import sys

# Returns minimum jumps needed from index i to reach end
def minJumpsRecur(i, arr):
    if i >= len(arr) - 1:
        return 0

    ans = sys.maxsize

    # Try all reachable positions from i
    for j in range(i + 1, min(i + arr[i] + 1, len(arr))):
        val = minJumpsRecur(j, arr)
        if val != sys.maxsize:
            ans = min(ans, 1 + val)

    return ans

def minJumps(arr):
    ans = minJumpsRecur(0, arr)
    return -1 if ans == sys.maxsize else ans 

if __name__ == "__main__": 
    arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
    print(minJumps(arr))
C# 
using System;
using System.Collections.Generic;

class GFG
{
    // Returns minimum jumps needed from index i to reach end
    static int minJumpsRecur(int i, List<int> arr)
    {
        if (i >= arr.Count - 1)
            return 0;

        int ans = int.MaxValue;

        // Try all reachable positions from i
        for (int j = i + 1; j <= i + arr[i] && j < arr.Count; j++)
        {
            int val = minJumpsRecur(j, arr);
            if (val != int.MaxValue)
                ans = Math.Min(ans, 1 + val);
        }

        return ans;
    }

    static int minJumps(List<int> arr)
    {
        int ans = minJumpsRecur(0, arr);
        return (ans == int.MaxValue) ? -1 : ans; 
    }

    static void Main()
    {
        List<int> arr = new List<int> {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        Console.WriteLine(minJumps(arr));
    }
}
JavaScript 
// Returns minimum jumps needed from index i to reach end
function minJumpsRecur(i, arr) {
    if (i >= arr.length - 1)
        return 0;

    let ans = Number.MAX_SAFE_INTEGER;

    // Try all reachable positions from i
    for (let j = i + 1; j <= i + arr[i] && j < arr.length; j++) {
        let val = minJumpsRecur(j, arr);
        if (val !== Number.MAX_SAFE_INTEGER)
            ans = Math.min(ans, 1 + val);
    }

    return ans;
}

function minJumps(arr) {
    let ans = minJumpsRecur(0, arr);
    return (ans === Number.MAX_SAFE_INTEGER) ? -1 : ans; 
}

// Driver Code
let arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
console.log(minJumps(arr));

Output
3

[Better] Using Bottom-Up DP (Tabulation) - O(n^2) Time and O(n) Space

For example in array, arr[] = {1, 3, 5, 8, 9, 2, 6,} minJumps(3) will be called two times as arr[3] is reachable from arr[1] and arr[2]. So this problem has both properties (optimal substructure and overlapping subproblems) of Dynamic Programming.

We create an array dp[] of size n, where each element dp[i] stores the minimum steps required to reach end of array from index i. Start from the last index i.e. n-1, and for each index i, compute the minimum steps for subarray i to n-1 and store the result in dp[i].

C++ 
#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Returns minimum jumps needed to reach end
int minJumps(vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, INT_MAX);

    dp[n - 1] = 0;

    for (int i = n - 2; i >= 0; i--) {
        // Try all reachable positions from i
        for (int j = i + 1; j <= i + arr[i] && j < n; j++) {
            if (dp[j] != INT_MAX)
                dp[i] = min(dp[i], 1 + dp[j]);
        }
    }

    return (dp[0] == INT_MAX) ? -1 : dp[0];
}

int main() {
    vector<int> arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    cout << minJumps(arr);
    return 0;
}
Java 
import java.util.List;
import java.util.Arrays;

class GFG {

    // Returns minimum jumps needed to reach end
    static int minJumps(List<Integer> arr) {
        int n = arr.size();
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        dp[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            // Try all reachable positions from i
            for (int j = i + 1; j <= i + arr.get(i) && j < n; j++) {
                if (dp[j] != Integer.MAX_VALUE)
                    dp[i] = Math.min(dp[i], 1 + dp[j]);
            }
        }

        return (dp[0] == Integer.MAX_VALUE) ? -1 : dp[0];
    }

    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9);
        System.out.println(minJumps(arr));
    }
}
Python 
import sys

# Returns minimum jumps needed to reach end
def minJumps(arr):
    n = len(arr)
    dp = [sys.maxsize] * n

    dp[n - 1] = 0

    for i in range(n - 2, -1, -1):
        # Try all reachable positions from i
        for j in range(i + 1, min(i + arr[i] + 1, n)):
            if dp[j] != sys.maxsize:
                dp[i] = min(dp[i], 1 + dp[j])

    return -1 if dp[0] == sys.maxsize else dp[0]

if __name__ == "__main__": 
    arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
    print(minJumps(arr))
C# 
using System;
using System.Collections.Generic;

class GFG
{
    // Returns minimum jumps needed to reach end
    static int minJumps(List<int> arr)
    {
        int n = arr.Count;
        int[] dp = new int[n];

        for (int i = 0; i < n; i++)
            dp[i] = int.MaxValue;

        dp[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--)
        {
            // Try all reachable positions from i
            for (int j = i + 1; j <= i + arr[i] && j < n; j++)
            {
                if (dp[j] != int.MaxValue)
                    dp[i] = Math.Min(dp[i], 1 + dp[j]);
            }
        }

        return (dp[0] == int.MaxValue) ? -1 : dp[0];
    }

    static void Main()
    {
        List<int> arr = new List<int> {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        Console.WriteLine(minJumps(arr));
    }
}
JavaScript 
// Returns minimum jumps needed to reach end
function minJumps(arr) {
    let n = arr.length;
    let dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);

    dp[n - 1] = 0;

    for (let i = n - 2; i >= 0; i--) {
        // Try all reachable positions from i
        for (let j = i + 1; j <= i + arr[i] && j < n; j++) {
            if (dp[j] !== Number.MAX_SAFE_INTEGER)
                dp[i] = Math.min(dp[i], 1 + dp[j]);
        }
    }

    return (dp[0] === Number.MAX_SAFE_INTEGER) ? -1 : dp[0];
}

// Driver Code 
let arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
console.log(minJumps(arr));

Output
3

[Expected] Using Greedy Approach - O(n) Time and O(1) Space

The core idea is to greedily track the farthest reachable index (maxReach). Instead of jumping at every step, keep moving within the current range. Only when you reach the end of that range, take a jump and extend the range to maxReach. This way, each jump covers the maximum possible distance, ensuring the minimum number of jumps.

For implementation, these variables are utilized during the iterative process:

  • jumps: Tracks the total jumps made.
  • currentReach: Represents the boundary of the current jump.
  • maxReach: Stores the furthest reachable index.

In each iteration, update maxReach as max(maxReach, i + arr[i]). When currentReach is reached, increase jumps and set currentReach to maxReach. If at any time i equals currentReach and maxReach is also equal to currentReach, it's impossible to reach the end, thus return -1.


C++ 
#include <iostream>
#include <vector>
using namespace std;

int minJumps(vector<int> &arr){
    int n = arr.size();

    if (arr[0] == 0)
        return -1;

    int maxReach = 0;
    int currReach = 0;
    int jump = 0;
    
    for (int i = 0; i < n; i++){
        maxReach = max(maxReach, i + arr[i]);
        if (maxReach >= n - 1){
            return jump + 1;
        }

        // Increment the Jump as we reached the
        // Current Reachable index
        if (i == currReach){

            // If Max reach is same as current index
            // then we can not jump further
            if (maxReach == i){
                return -1;
            }

            // If maxReach > current index then increment
            // jump and update current reachable index
            else{
                jump++;
                currReach = maxReach;
            }
        }
    }

    return -1;
}

int main()
{
   vector<int> arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    cout << minJumps(arr);
    return 0;
}
Java 
class GfG {

    static int minJumps(int[] arr){
        int n = arr.length;
        if (arr[0] == 0)
            return -1;
        int maxReach = 0;
        int currReach = 0;
        int jump = 0;
        for (int i = 0; i < n; i++) {
            maxReach = Math.max(maxReach, i + arr[i]);

            if (maxReach >= n - 1) {
                return jump + 1;
            }

            // Increment the Jump as we reached the
            // Current Reachable index
            if (i == currReach) {

                // If Max reach is same as current index
                // then we can not jump further
                if (i == maxReach) {
                    return -1;
                }

                // If Max reach > current index then
                // increment jump and update current
                // reachable index
                else {
                    jump++;
                    currReach = maxReach;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args)
    {
        int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        System.out.println(minJumps(arr));
    }
}
Python 
def minJumps(arr):
    n = len(arr)
    if arr[0] == 0:
        return -1
    maxReach = 0
    currReach = 0
    jump = 0
    for i in range(n):
        maxReach = max(maxReach, i + arr[i])

        if maxReach >= n - 1:
            return jump + 1

        # Increment the Jump as we reached the
        # Current Reachable index
        if i == currReach:

            # If Max reach is same as current index
            # then we can not jump further
            if i == maxReach:
                return -1

            # If Max reach > current index then increment
            # jump and update current reachable index
            else:
                jump += 1
                currReach = maxReach

    return -1


if __name__ == "__main__":
    arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
    print(minJumps(arr))
C# 
using System;

class GfG {
    static int minJumps(int[] arr)
    {
        int n = arr.Length;
        if (arr[0] == 0)
            return -1;
        int maxReach = 0;
        int currReach = 0;
        int jump = 0;
        for (int i = 0; i < n; i++) {
            maxReach = Math.Max(maxReach, i + arr[i]);
            if (maxReach >= n - 1) {
                return jump + 1;
            }

            // Increment the Jump as we reached the
            // Current Reachable index
            if (i == currReach) {

                // If Max reach is same as current index
                // then we can not jump further
                if (i == maxReach) {
                    return -1;
                }

                // If Max reach > current index then
                // increment jump and update current
                // reachable index
                else {
                    jump++;
                    currReach = maxReach;
                }
            }
        }

        return -1;
    }

    static void Main()
    {
        int[] arr = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        Console.WriteLine(minJumps(arr));
    }
}
JavaScript 
function minJumps(arr)
{
    let n = arr.length;

    if (arr[0] === 0)
        return -1;
    let maxReach = 0;
    let currReach = 0;
    let jump = 0;
    for (let i = 0; i < n; i++) {
        maxReach = Math.max(maxReach, i + arr[i]);
        if (maxReach >= n - 1) {
            return jump + 1;
        }

        // Increment the Jump as we reached the
        // Current Reachable index
        if (i === currReach) {

            // If Max reach is same as current index
            // then we can not jump further
            if (i === maxReach) {
                return -1;
            }

            // If Max reach > current index then increment
            // jump and update current reachable index
            else {
                jump++;
                currReach = maxReach;
            }
        }
    }

    return -1;
}

// Driver Code
const arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9];
console.log(minJumps(arr));

Output
3
Comment

Explore