Data Modelling & AI Data Structure & Algorithm

Minimum number of jumps to reach end | Set 2 (O(n) solution)

20 June 2025

2

Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then we cannot move through that element. If we can’t reach the end, return -1.
Prerequisite: Minimum number of jumps to reach end | Set-1 ( O(n²) solution)

Examples:

Input: arr[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}
Output: 3 (1-> 3 -> 8 -> 9)
Explanation: Jump from 1st element to 2nd element as there is only 1 step, now there are three options 5, 8 or 9. If 8 or 9 is chosen then the end node 9 can be reached. So 3 jumps are made.

Input : arr[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output: 10
Explanation: In every step a jump is needed so the count of jumps is 10.

Minimum number of jumps to reach end using Greedy approach:

The idea is to use greedy approach to find the minimum jumps needed to reach the end of an array by iterating through the array while maintaining the maximum reachable index and the remaining steps in the current jump and updating these values based on the array elements.

Follow the steps below to solve the problem:

Initialize the variables maxReach, step, and jump to keep track of the maximum reachable index, the remaining steps at the current position, and the number of jumps taken, respectively.
Traverse the array and update the maximum reachable index based on the sum of the current index and its corresponding array value. This helps determine how far the current jump can take us.
If the remaining steps for the current jump are exhausted, a new jump is initiated.
If the current index surpasses the maximum reachable index, indicating no further progress, -1 is returned meaning no solution is found.

Below is the implementation of above approach:

C++

// C++ program to count Minimum number
// of jumps to reach end
#include <bits/stdc++.h>
using namespace std;
 
int max(int x, int y)
{
    return (x > y) ? x : y;
}
 
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
 
    // The number of jumps needed to
    // reach the starting index is 0
    if (n <= 1)
        return 0;
       
      //If value of first index guarantees 
      //only 1 jump is needed, return 1
      if (arr[0] >= n-1)
          return 1;
 
    // Return -1 if not possible to jump
    if (arr[0] == 0)
        return -1;
 
    // initialization
    // stores all time the maximal
    // reachable index in the array.
    int maxReach = arr[0];
 
    // stores the number of steps
    // we can still take
    int step = arr[0];
 
    // stores the number of jumps
    // necessary to reacach that maximal
    // reachable position.
    int jump = 1;
 
    // Start traversing array
    int i = 1;
    for (i = 1; i < n; i++) {
        // Check if we have reached the end of the array
        if (i == n - 1)
            return jump;
       
         //Check if value at current index guarantees jump to end
          if (arr[i] >= (n-1) - i)
              return jump + 1;
 
        // updating maxReach
        maxReach = max(maxReach, i + arr[i]);
 
        // we use a step to get to the current index
        step--;
 
        // If no further steps left
        if (step == 0) {
            // we must have used a jump
            jump++;
 
            // Check if the current index/position or lesser index
            // is the maximum reach point from the previous indexes
            if (i >= maxReach)
                return -1;
 
            // re-initialize the steps to the amount
            // of steps to reach maxReach from position i.
            step = maxReach - i;
        }
    }
 
    return -1;
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    int size = sizeof(arr) / sizeof(int);
 
    // Calling the minJumps function
    cout << ("Minimum number of jumps to reach end is %d ",
             minJumps(arr, size));
    return 0;
}
// This code is contributed by
// Shashank_Sharma

C

// C program to count Minimum number
// of jumps to reach end
#include <stdio.h>
 
int max(int x, int y) { return (x > y) ? x : y; }
 
// Returns minimum number of jumps
// to reach arr[n-1] from arr[0]
int minJumps(int arr[], int n)
{
 
    // The number of jumps needed to
    // reach the starting index is 0
    if (n <= 1)
        return 0;
   
      //If value of first index guarantees 
      //only 1 jump is needed, return 1
      if (arr[0] >= n-1)
          return 1;
 
    // Return -1 if not possible to jump
    if (arr[0] == 0)
        return -1;
 
    // initialization
    // stores all time the maximal
    // reachable index in the array.
    int maxReach = arr[0];
 
    // stores the number of steps
    // we can still take
    int step = arr[0];
 
    // stores the number of jumps
    // necessary to reach that maximal
    // reachable position.
    int jump = 1;
 
    // Start traversing array
    int i = 1;
    for (i = 1; i < n; i++) {
        // Check if we have reached the end of the array
        if (i == n - 1)
            return jump;
         
          //Check if value at current index guarantees jump to end
          if (arr[i] >= (n-1) - i)
              return jump + 1;
           
        // updating maxReach
        maxReach = max(maxReach, i + arr[i]);
 
        // we use a step to get to the current index
        step--;
 
        // If no further steps left
        if (step == 0) {
            // we must have used a jump
            jump++;
 
            // Check if the current index/position or lesser index
            // is the maximum reach point from the previous indexes
            if (i >= maxReach)
                return -1;
 
            // re-initialize the steps to the amount
            // of steps to reach maxReach from position i.
            step = maxReach - i;
        }
    }
    return -1;
}
 
// Driver program to test above function
int main()
{
    int arr[] = { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
    int size = sizeof(arr) / sizeof(int);
 
    // Calling the minJumps function
    printf(
        "Minimum number of jumps to reach end is %d ",
        minJumps(arr, size));
    return 0;
}
// This code is contributed by Abhishek Kumar Singh

Java

// Java program to count Minimum number
// of jumps to reach end
 
class Test {
    static int minJumps(int arr[])
    {
        if (arr.length <= 1)
            return 0;
       
          //If value of first index guarantees 
          //only 1 jump is needed, return 1
        if (arr[0] >= arr.length-1)
            return 1;
 
        // Return -1 if not possible to jump
        if (arr[0] == 0)
            return -1;
 
        // initialization
        int maxReach = arr[0];
        int step = arr[0];
        int jump = 1;
 
        // Start traversing array
        for (int i = 1; i < arr.length; i++) {
            // Check if we have reached 
// the end of the array
            if (i == arr.length - 1)
                return jump;
           
          //Check if value at current index guarantees jump to end
            if (arr[i] >= (arr.length-1) - i)
                return jump + 1;
 
            // updating maxReach
            maxReach = Math.max(maxReach, i + arr[i]);
 
            // we use a step to get to the current index
            step--;
 
            // If no further steps left
            if (step == 0) {
                // we must have used a jump
                jump++;
 
                // Check if the current 
// index/position or lesser index
                // is the maximum reach point 
// from the previous indexes
                if (i >= maxReach)
                    return -1;
 
                // re-initialize the steps to the amount
                // of steps to reach maxReach from position i.
                step = maxReach - i;
            }
        }
 
        return -1;
    }
 
    // Driver method to test the above function
    public static void main(String[] args)
    {
        int arr[] = new int[] { 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9 };
 
        // calling minJumps method
        System.out.println(minJumps(arr));
    }
}

Python3

# python program to count Minimum number
# of jumps to reach end
  
# Returns minimum number of jumps to reach arr[n-1] from arr[0]
def minJumps(arr, n):
  # The number of jumps needed to reach the starting index is 0
  if (n <= 1):
    return 0
   
  #If value of first index guarantees only 1 jump is needed, return 1
  if (arr[0] >= n-1):
      return 1
  
  # Return -1 if not possible to jump
  if (arr[0] == 0):
    return -1
  
  # initialization
  # stores all time the maximal reachable index in the array
  maxReach = arr[0]  
  # stores the amount of steps we can still take
  step = arr[0]
  # stores the amount of jumps necessary to reach that maximal reachable position
  jump = 1
  
  # Start traversing array
  
  for i in range(1, n):
    # Check if we have reached the end of the array
    if (i == n-1):
      return jump
     
    #Check if value at current index guarantees jump to end
    if (arr[i] >= (n-1) - i):
        return jump + 1
  
    # updating maxReach
    maxReach = max(maxReach, i + arr[i])
  
    # we use a step to get to the current index
    step -= 1;
  
    # If no further steps left
    if (step == 0):
      # we must have used a jump
      jump += 1
       
      # Check if the current index / position or lesser index
      # is the maximum reach point from the previous indexes
      if(i >= maxReach):
        return -1
  
      # re-initialize the steps to the amount
      # of steps to reach maxReach from position i.
      step = maxReach - i;
  return -1
  
 
# Driver program to test above function
arr = [1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9]
size = len(arr)
  
# Calling the minJumps function
print("Minimum number of jumps to reach end is % d " % minJumps(arr, size))
 
# This code is contributed by Aditi Sharma

C#

// C# program to count Minimum
// number of jumps to reach end
using System;
 
class GFG {
    static int minJumps(int[] arr)
    {
        if (arr.Length <= 1)
            return 0;
 
        // Return -1 if not
        // possible to jump
        if (arr[0] == 0)
            return -1;
 
        // initialization
        int maxReach = arr[0];
        int step = arr[0];
        int jump = 1;
 
        // Start traversing array
        for (int i = 1; i < arr.Length; i++) {
            // Check if we have reached
            // the end of the array
            if (i == arr.Length - 1)
                return jump;
 
            // updating maxReach
            maxReach = Math.Max(maxReach, i + arr[i]);
 
            // we use a step to get
            // to the current index
            step--;
 
            // If no further steps left
            if (step == 0) {
                // we must have used a jump
                jump++;
 
                // Check if the current index/position
                // or lesser index is the maximum reach
                // point from the previous indexes
                if (i >= maxReach)
                    return -1;
 
                // re-initialize the steps to
                // the amount of steps to reach
                // maxReach from position i.
                step = maxReach - i;
            }
        }
 
        return -1;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = new int[] { 1, 3, 5, 8, 9, 2,
                                6, 7, 6, 8, 9 };
 
        // calling minJumps method
        Console.Write(minJumps(arr));
    }
}
 
// This code is contributed
// by nitin mittal

Javascript

<script>
     
// Javascript program to count Minimum number
  
// Returns minimum number of jumps
 
// to reach arr[n-1] from arr[0]
 
function minJumps(arr,n)
 
{
 
    // The number of jumps needed to
 
    // reach the starting index is 0
 
    if (n <= 1)
 
        return 0;
 
    // Return -1 if not possible to jump
 
    if (arr[0] == 0)
 
        return -1;
 
    // initialization
 
    // stores all time the maximal
 
    // reachable index in the array.
 
    let maxReach = arr[0];
 
    // stores the number of steps
 
    // we can still take
 
    let step = arr[0];
 
    // stores the number of jumps
 
    // necessary to reach that maximal
 
    // reachable position.
 
    let jump = 1;
 
    // Start traversing array
 
    let i = 1;
 
    for (i = 1; i < n; i++) {
 
        // Check if we have reached the end of the array
 
        if (i == n - 1)
 
            return jump;
 
        // updating maxReach
 
        maxReach =Math.max(maxReach, i + arr[i]);
 
        // we use a step to get to the current index
 
        step--;
 
        // If no further steps left
 
        if (step == 0) {
 
            // we must have used a jump
 
            jump++;
 
            // Check if the current index/position or lesser index
 
            // is the maximum reach point from the previous indexes
 
            if (i >= maxReach)
 
                return -1;
 
            // re-initialize the steps to the amount
 
            // of steps to reach maxReach from position i.
 
            step = maxReach - i;
 
        }
 
    }
 
    return -1;
 
}
 
// Driver program to test above function
 
    var arr = [ 1, 3, 5, 8, 9, 2, 6, 7, 6, 8,9 ];
 
    let size = arr.length;
 
    // Calling the minJumps function
 
    document.write("Minimum number of jumps to reach end is "+
 
             minJumps(arr, size));
 
// This code is contributed by
 
// Potta Lokesh
 
</script>

PHP

<?php 
// PHP program to count Minimum number
// of jumps to reach end
  
// Returns minimum number of jumps to reach arr[n-1] from arr[0]
function minJumps(&$arr, $n)
{
      
    // The number of jumps needed to reach the starting index is 0
    if ($n <= 1)
        return 0;
  
    // Return -1 if not possible to jump
    if ($arr[0] == 0)
        return -1;
  
    // initialization
    // stores all time the maximal reachable index in the array.
    $maxReach = $arr[0]; 
 
    // stores the number of steps we can still take 
    $step = $arr[0]; 
 
    //stores the number of jumps necessary to reach that
    //  maximal reachable position.     
    $jump =1;
 
    // Start traversing array
    $i=1;
    for ($i = 1; $i < $n; $i++)
    {
        // Check if we have reached the end of the array
        if ($i == $n-1)
            return $jump;
  
        // updating maxReach
        $maxReach = max($maxReach, $i+$arr[$i]);
  
        // we use a step to get to the current index
        $step--;
  
        // If no further steps left
        if ($step == 0)
        {
            // we must have used a jump
            $jump++;
  
            // Check if the current index/position or lesser index
            // is the maximum reach point from the previous indexes
            if($i >= $maxReach)
                return -1;
  
            // re-initialize the steps to the amount
            // of steps to reach maxReach from position i.
            $step = $maxReach - $i;
        }
    }
  
    return -1;
}
  
// Driver program to test above function
 
$arr=array(1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9);
$size = sizeof($arr)/sizeof($arr[0]);
  
// Calling the minJumps function
echo "Minimum number of jumps to reach end is "
     . minJumps($arr, $size);
return 0;
// This code is contributed by Ita_c.
?>

Output

Complexity Analysis:

Time complexity: O(n), Only one traversal of the array is needed.
Auxiliary Space: O(1), There is no space required.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Minimum number of jumps to reach end | Set 2 (O(n) solution)

Minimum number of jumps to reach end using Greedy approach:

C++

C

Java

Python3

C#

Javascript

PHP

Is MCP Already Outdated? The Real Reason Anthropic Shipped Skills—and How to Pair Them with Milvus

Unlocking 8× Milvus Performance with Cloudian HyperStore and NVIDIA RDMA for S3 Storage

Power high performance RAG for GenAI with HPE Alletra Storage MP + Milvus

LEAVE A REPLY Cancel reply

Most Popular

Why I refuse to upgrade my smart watch. [Video]

Quick Share is now compatible with Apple’s AirDrop

Upgrade your home hydration with Waterdrop Filter this Black Friday

Google’s finally learning how to sync Android’s Airplane Mode with Wear OS

EDITOR PICKS

Why I refuse to upgrade my smart watch. [Video]

Quick Share is now compatible with Apple’s AirDrop

Upgrade your home hydration with Waterdrop Filter this Black Friday

POPULAR POSTS

Why I refuse to upgrade my smart watch. [Video]

Quick Share is now compatible with Apple’s AirDrop

Upgrade your home hydration with Waterdrop Filter this Black Friday

POPULAR CATEGORY

ABOUT US

FOLLOW US