Paths requiring minimum number of jumps to reach end of array

19 June 2025

0

Given an array arr[], where each element represents the maximum number of steps that can be made forward from that element, the task is to print all possible paths that require the minimum number of jumps to reach the end of the given array starting from the first array element.

Note: If an element is 0, then there are no moves allowed from that element.

Examples:

Input: arr[] = {1, 1, 1, 1, 1}
Output:
0 ? 1 ? 2 ? 3 ?4
Explanation:
In every step, only one jump is allowed.
Therefore, only one possible path exists to reach end of the array.

Input: arr[] = {3, 3, 0, 2, 1, 2, 4, 2, 0, 0}
Output:
0 ? 3 ? 5 ? 6 ? 9
0 ? 3 ? 5 ? 7 ? 9

Approach: The idea is to use Dynamic Programming to solve this problem. Follow the steps below to solve the problem:

Initialize an array dp[] of size N, where dp[i] stores the minimum number of jumps required to reach the end of the array arr[N – 1] from the index i
Compute the minimum number of steps required for each index to reach the end of the array by iterating over indices N – 2 to 1. For each index, try out all possible steps that can be taken from that index, i.e. [1, arr[i]].
While trying out all the possible steps by iterating over [1, arr[i]], for each index, update and store the minimum value of dp[i + j].
Initialize a queue of Pair class instance, which stores the index of the current position and the path that has been traveled so far to reach that index.
Keep updating the minimum number of steps required and finally, print the paths corresponding to those required count of steps.

Below is the implementation of the above approach:

C++

// C++ program to implement the
// above approach
#include <bits/stdc++.h>
using namespace std;
 
// Pair Struct
struct Pair
{
     
    // Stores the current index
    int idx;
 
    // Stores the path
    // travelled so far
    string psf;
 
    // Stores the minimum jumps
    // required to reach the
    // last index from current index
    int jmps;
};
 
// Minimum jumps required to reach
// end of the array
void minJumps(int arr[], int dp[], int n)
{
    for(int i = 0; i < n; i++)
        dp[i] = INT_MAX;
 
    dp[n - 1] = 0;
 
    for(int i = n - 2; i >= 0; i--)
    {
         
        // Stores the maximum number
        // of steps that can be taken
        // from the current index
        int steps = arr[i];
        int min = INT_MAX;
 
        for(int j = 1; 
                j <= steps && i + j < n;
                j++) 
        {
             
            // Checking if index stays
            // within bounds
            if (dp[i + j] != INT_MAX && 
                dp[i + j] < min) 
            {
                 
                // Stores the minimum
                // number of jumps
                // required to jump
                // from (i + j)-th index
                min = dp[i + j];
            }
        }
         
        if (min != INT_MAX)
            dp[i] = min + 1;
    }
}
 
// Function to find all possible
// paths to reach end of array
// requiring minimum number of steps
void possiblePath(int arr[], int dp[], int n)
{
    queue<Pair> Queue;
    Pair p1 = { 0, "0", dp[0] };
    Queue.push(p1);
 
    while (Queue.size() > 0)
    {
        Pair tmp = Queue.front();
        Queue.pop();
 
        if (tmp.jmps == 0)
        {
            cout << tmp.psf << "\n";
            continue;
        }
 
        for(int step = 1; 
                step <= arr[tmp.idx]; 
                step++)
        {
            if (tmp.idx + step < n && 
                tmp.jmps - 1 == dp[tmp.idx + step])
            {
                 
                // Storing the neighbours
                // of current index element
                string s1 = tmp.psf + " -> " + 
                 to_string((tmp.idx + step));
                  
                Pair p2 = { tmp.idx + step, s1, 
                           tmp.jmps - 1 };
                           
                Queue.push(p2);
            }
        }
    }
}
 
// Function to find the minimum steps
// and corresponding paths to reach
// end of an array
void Solution(int arr[], int dp[], int size)
{
     
    // dp[] array stores the minimum jumps
    // from each position to last position
    minJumps(arr, dp, size);
 
    possiblePath(arr, dp, size);
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 3, 0, 2, 1,
                  2, 4, 2, 0, 0 };
 
    int size = sizeof(arr) / sizeof(arr[0]);
    int dp[size];
 
    Solution(arr, dp, size);
}
 
// This code is contributed by akhilsaini

Java

// Java Program to implement the
// above approach
 
import java.util.*;
class GFG {
 
    // Pair Class instance
    public static class Pair {
        // Stores the current index
        int idx;
 
        // Stores the path
        // travelled so far
        String psf;
 
        // Stores the minimum jumps
        // required to reach the
        // last index from current index
        int jmps;
 
        // Constructor
        Pair(int idx, String psf, int jmps)
        {
            this.idx = idx;
            this.psf = psf;
            this.jmps = jmps;
        }
    }
 
    // Minimum jumps required to reach
    // end of the array
    public static int[] minJumps(int[] arr)
    {
        int dp[] = new int[arr.length];
 
        Arrays.fill(dp, Integer.MAX_VALUE);
 
        int n = dp.length;
 
        dp[n - 1] = 0;
 
        for (int i = n - 2; i >= 0; i--) {
            // Stores the maximum number
            // of steps that can be taken
            // from the current index
            int steps = arr[i];
            int min = Integer.MAX_VALUE;
 
            for (int j = 1; j <= steps && i + j < n; j++) {
                // Checking if index stays
                // within bounds
                if (dp[i + j] != Integer.MAX_VALUE
                    && dp[i + j] < min) {
                    // Stores the minimum
                    // number of jumps
                    // required to jump
                    // from (i + j)-th index
                    min = dp[i + j];
                }
            }
 
            if (min != Integer.MAX_VALUE)
                dp[i] = min + 1;
        }
        return dp;
    }
 
    // Function to find all possible
    // paths to reach end of array
    // requiring minimum number of steps
    public static void possiblePath(
        int[] arr, int[] dp)
    {
 
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(0, "" + 0, dp[0]));
 
        while (queue.size() > 0) {
            Pair tmp = queue.remove();
 
            if (tmp.jmps == 0) {
                System.out.println(tmp.psf);
                continue;
            }
 
            for (int step = 1;
                 step <= arr[tmp.idx];
                 step++) {
 
                if (tmp.idx + step < arr.length
                    && tmp.jmps - 1 == dp[tmp.idx + step]) {
                    // Storing the neighbours
                    // of current index element
                    queue.add(new Pair(
                        tmp.idx + step,
                        tmp.psf + " -> " + (tmp.idx + step),
                        tmp.jmps - 1));
                }
            }
        }
    }
 
    // Function to find the minimum steps
    // and corresponding paths to reach
    // end of an array
    public static void Solution(int arr[])
    {
        // Stores the minimum jumps from
        // each position to last position
        int dp[] = minJumps(arr);
 
        possiblePath(arr, dp);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 3, 3, 0, 2, 1,
                      2, 4, 2, 0, 0 };
        int size = arr.length;
        Solution(arr);
    }
}

Python3

# Python3 program to implement the
# above approach
from queue import Queue
import sys
 
# Pair Class instance
class Pair(object):
     
    # Stores the current index
    idx = 0
 
    # Stores the path
    # travelled so far
    psf = ""
 
    # Stores the minimum jumps
    # required to reach the
    # last index from current index
    jmps = 0
 
    # Constructor
    def __init__(self, idx, psf, jmps):
         
        self.idx = idx
        self.psf = psf
        self.jmps = jmps
 
# Minimum jumps required to reach
# end of the array
def minJumps(arr):
 
    MAX_VALUE = sys.maxsize
    dp = [MAX_VALUE for i in range(len(arr))]
 
    n = len(dp)
 
    dp[n - 1] = 0
 
    for i in range(n - 2, -1, -1):
         
        # Stores the maximum number
        # of steps that can be taken
        # from the current index
        steps = arr[i]
        minimum = MAX_VALUE
 
        for j in range(1, steps + 1, 1):
            if i + j >= n:
                break
             
            # Checking if index stays
            # within bounds
            if ((dp[i + j] != MAX_VALUE) and
                (dp[i + j] < minimum)):
                     
                # Stores the minimum
                # number of jumps
                # required to jump
                # from (i + j)-th index
                minimum = dp[i + j]
 
        if minimum != MAX_VALUE:
            dp[i] = minimum + 1
             
    return dp
 
# Function to find all possible
# paths to reach end of array
# requiring minimum number of steps
def possiblePath(arr, dp):
 
    queue = Queue(maxsize = 0)
    p1 = Pair(0, "0", dp[0])
    queue.put(p1)
 
    while queue.qsize() > 0:
        tmp = queue.get()
 
        if tmp.jmps == 0:
            print(tmp.psf)
            continue
 
        for step in range(1, arr[tmp.idx] + 1, 1):
            if ((tmp.idx + step < len(arr)) and
               (tmp.jmps - 1 == dp[tmp.idx + step])):
               
                # Storing the neighbours
                # of current index element
                p2 = Pair(tmp.idx + step, tmp.psf +
                           " -> " + str((tmp.idx + step)),
                         tmp.jmps - 1)
                          
                queue.put(p2)
 
# Function to find the minimum steps
# and corresponding paths to reach
# end of an array
def Solution(arr):
     
    # Stores the minimum jumps from
    # each position to last position
    dp = minJumps(arr)
     
    possiblePath(arr, dp)
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 3, 3, 0, 2, 1, 
            2, 4, 2, 0, 0 ]
    size = len(arr)
 
    Solution(arr)
 
# This code is contributed by akhilsaini

C#

// C# program to implement the
// above approach
using System;
using System.Collections;
 
// Pair Struct
public struct Pair
{
     
    // Stores the current index
    public int idx;
 
    // Stores the path
    // travelled so far
    public string psf;
 
    // Stores the minimum jumps
    // required to reach the
    // last index from current index
    public int jmps;
 
    // Constructor
    public Pair(int idx, String psf, int jmps)
    {
        this.idx = idx;
        this.psf = psf;
        this.jmps = jmps;
    }
}
 
class GFG{
 
// Minimum jumps required to reach
// end of the array
public static int[] minJumps(int[] arr)
{
    int[] dp = new int[arr.Length];
    int n = dp.Length;
 
    for(int i = 0; i < n; i++)
        dp[i] = int.MaxValue;
 
    dp[n - 1] = 0;
 
    for(int i = n - 2; i >= 0; i--)
    {
         
        // Stores the maximum number
        // of steps that can be taken
        // from the current index
        int steps = arr[i];
        int min = int.MaxValue;
 
        for(int j = 1; 
                j <= steps && i + j < n;
                j++)
        {
             
            // Checking if index stays
            // within bounds
            if (dp[i + j] != int.MaxValue && 
                dp[i + j] < min)
            {
                 
                // Stores the minimum
                // number of jumps
                // required to jump
                // from (i + j)-th index
                min = dp[i + j];
            }
        }
 
        if (min != int.MaxValue)
            dp[i] = min + 1;
    }
    return dp;
}
 
// Function to find all possible
// paths to reach end of array
// requiring minimum number of steps
public static void possiblePath(int[] arr,
                                int[] dp)
{
    Queue queue = new Queue();
    queue.Enqueue(new Pair(0, "0", dp[0]));
 
    while (queue.Count > 0)
    {
        Pair tmp = (Pair)queue.Dequeue();
 
        if (tmp.jmps == 0) 
        {
            Console.WriteLine(tmp.psf);
            continue;
        }
 
        for(int step = 1; 
                step <= arr[tmp.idx];
                step++) 
        {
            if (tmp.idx + step < arr.Length && 
               tmp.jmps - 1 == dp[tmp.idx + step]) 
            {
                 
                // Storing the neighbours
                // of current index element
 
                queue.Enqueue(new Pair(
                    tmp.idx + step,
                    tmp.psf + " -> " + 
                   (tmp.idx + step),
                   tmp.jmps - 1));
            }
        }
    }
}
 
// Function to find the minimum steps
// and corresponding paths to reach
// end of an array
public static void Solution(int[] arr)
{
     
    // Stores the minimum jumps from
    // each position to last position
    int[] dp = minJumps(arr);
 
    possiblePath(arr, dp);
}
 
// Driver Code
static public void Main()
{
    int[] arr = { 3, 3, 0, 2, 1,
                  2, 4, 2, 0, 0 };
    int size = arr.Length;
     
    Solution(arr);
}
}
 
// This code is contributed by akhilsaini

Javascript

//JS code for the above approach
class Pair
{
 
    // Stores the current index
    idx;
 
    // Stores the path
    // travelled so far
    psf;
 
    // Stores the minimum jumps
    // required to reach the
    // last index from current index
    jmps;
 
    // Constructor
    constructor(idx, psf, jmps) {
        this.idx = idx;
        this.psf = psf;
        this.jmps = jmps;
    }
}
 
// Minimum jumps required to reach
// end of the array
function minJumps(arr) {
    const MAX_VALUE = Number.MAX_SAFE_INTEGER;
    const dp = Array(arr.length).fill(MAX_VALUE);
 
    const n = dp.length;
 
    dp[n - 1] = 0;
 
    for (let i = n - 2; i >= 0; i--)
    {
     
        // Stores the maximum number
        // of steps that can be taken
        // from the current index
        const steps = arr[i];
        let minimum = MAX_VALUE;
 
        for (let j = 1; j <= steps; j++) {
            if (i + j >= n) break;
 
            // Checking if index stays
            // within bounds
            if (dp[i + j] !== MAX_VALUE && dp[i + j] < minimum)
            {
             
                // Stores the minimum
                // number of jumps
                // required to jump
                // from (i + j)-th index
                minimum = dp[i + j];
            }
        }
 
        if (minimum !== MAX_VALUE) dp[i] = minimum + 1;
    }
    return dp;
}
 
// Function to find all possible
// paths to reach end of array
// requiring minimum number
function possiblePath(arr, dp) {
const queue = [];
queue.push(new Pair(0, "0", dp[0]));
 
while (queue.length > 0) {
    const tmp = queue.shift();
 
    if (tmp.jmps === 0) {
        document.write(tmp.psf +"<br>");
        continue;
    }
 
    for (let step = 1; step <= arr[tmp.idx]; step++)
    {
        if (tmp.idx + step < arr.length && tmp.jmps - 1 === dp[tmp.idx + step])
        {
         
            // Storing the neighbours
            // of current index element
            queue.push(new Pair(tmp.idx + step, tmp.psf + " -> " + (tmp.idx + step), tmp.jmps - 1));
        }
    }
}
}
 
// Function to find the minimum steps
// and corresponding paths to reach
// end of an array
function Solution(arr)
{
 
// Stores the minimum jumps from
// each position to last position
const dp = minJumps(arr);
 
possiblePath(arr, dp);
}
 
// Driver Code
const arr = [3, 3, 0, 2, 1, 2, 4, 2, 0, 0];
const size = arr.length;
Solution(arr);
 
// This code is contributed by lokeshpotta20.

Output:

0 -> 3 -> 5 -> 6 -> 9
0 -> 3 -> 5 -> 7 -> 9

Time Complexity: O(N²)
Auxiliary Space: O(N)

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!

Paths requiring minimum number of jumps to reach end of array

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US