Minimum jumps required to reach all array elements using largest element

0 0 12 minutes read

Given an array arr[] of N distinct integer, the task is to find the minimum number of jumps required from the largest element to reach all array elements such that a jump is possible from the i^th element to the j^th element if the value of arr[i] is greater than arr[j] and value of arr[j] is greater than all other elements between the i^th and j^th element.

Examples:

Input: arr[] = {1, 3, 6, 5}
Output: [2, 1, 0, 1]Explanation:
Below are the jumps required to reach each platform:

For the 1st platform, the jump from the 3rd platform to the 2nd platform, then jump to the 1st platform is required. Hence, a total of 2 jumps are required.

For the 2nd platform, the jump from the 3rd platform directly to the 2nd platform is required. Hence, a total of 1 jump are required.

For the 3rd platform, we are already on the 3rd platform. Hence, a total of 0 jumps are required.

For the 4th platform, the jump from the 3rd platform directly to the 4th platform is required. Hence, a total of 1 jump are required.

Input: arr[] = {3, 5}
Output: [1, 0]

Approach: The given problem can be solved using Dynamic Programming which is based on the observation that the minimum jump possible from the largest element to the i^th element is one greater than the minimum of minimum jumps required for the next greater element in the left or right. So, the idea is to precompute the results of larger elements and use them to find answers to smaller elements. Follow the steps below to solve the given problem:

For each array element arr[i] store the two indices L and R representing the index of the next greater element to the left and right in the map respectively.
Sort the array arr[] in descending order.
Initialize a vector, say ans[] that stores the minimum jumps for all array elements.
Traverse the array arr[] and perform the following steps:
- If the current array element is the largest element then 0 jumps are required for the current element.
- Find the distance of the next greater element to the left and right of the current element using the value stored in the maps. Store the distances in the variables, L and R respectively.
- Update the value of minimum jumps, say M as per the following criteria:
  - If L is at least 0 and R is less than N, then the value of M is min(ans[L], ans[R]) + 1.
  - If L is less than 0 and R is less than N, then the value of M is ans[R] + 1.
  - If L is at least 0 and R is at least N, then the value of M is ans[L] + 1.
- Update the value of minimum jumps for the current index as the value of M.
After completing the above steps, print the array ans[] as the resultant jumps of indices.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ar array
 
// Function to find next greater element
// to left and right of current element
ar<int, 2> expand(int idx, vector<int>& A)
{
 
    // Starting l and r from previous
    // and the next element of the
    // current element
    int l = idx - 1;
    int r = idx + 1;
 
    // FInd the next greater element
    // to the left
    while (l >= 0) {
 
        if ((int)(A[idx]) > A[l]) {
            --l;
        }
        else {
            break;
        }
    }
 
    if (l < 0 || l == idx) {
        l = -2;
    }
 
    // Find the next greater element
    // to the right
    while (r < (int)(A.size())) {
        if ((int)A[idx] > A[r]) {
            ++r;
        }
        else {
            break;
        }
    }
 
    if (r >= (int)(A.size()) || r == idx) {
        r = -2;
    }
 
    // Return l and r in the form of
    // array of size 2
    return { l, r };
}
 
// Function to find the minimum jumps
// required to reach to all elements from
// the largest element
vector<int> minJumps(int N, vector<int>& A)
{
    vector<int> ans(N, 0);
 
    // Stores the mapping from index
    // to the element in array A[]
    map<int, ar<int, 2> > mp;
 
    map<int, int> iToA;
    map<int, int> AToi;
 
    // Stores largest array element
    int big = A[0];
 
    // Find the two indices l, r such
    // that A[l] > A[i] < A[r] and
    // l<i<r using expand function
    for (int i = 0; i < N; ++i) {
        big = max({ big, A[i] });
        mp[i] = expand(i, A);
 
        iToA[i] = A[i];
        AToi[A[i]] = i;
    }
 
    // sorting A in descending order
    sort(A.begin(), A.end(), greater<int>());
 
    for (int i = 0; i < A.size(); ++i) {
 
        // Stores the resultant minimum
        // jumps required
        int m;
 
        // Check if the current element
        // is largest or not
        if (A[i] == big) {
            int cur = AToi[A[i]];
            ans[cur] = 0;
            continue;
        }
 
        // Find the answer to the
        // current element
        int cur = AToi[A[i]];
        int l = mp[cur][0];
        int r = mp[cur][1];
 
        if (l >= 0 && r < N) {
            m = min(ans[l], ans[r]) + 1;
        }
        else if (l < 0 && r < N) {
            m = ans[r] + 1;
        }
        else if (l >= 0 && r >= N) {
            m = ans[l] + 1;
        }
 
        // Update the resultant minimum
        // jumps for the current element
        ans[cur] = m;
    }
 
    // Return the result
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> arr = { 5, 1, 3, 4, 7 };
    int N = arr.size();
 
    vector<int> out = minJumps(N, arr);
 
    // Print the result
    for (auto& it : out)
        cout << it << ' ';
 
    return 0;
}

Java

import java.util.*;
import java.io.*;
 
// Java program for the above approach
class GFG{
 
    // Function to find next greater element
    // to left and right of current element
    public static ArrayList<Integer> expand(int idx, ArrayList<Integer> A)
    {
 
        // Starting l and r from previous
        // and the next element of the
        // current element
        int l = idx - 1;
        int r = idx + 1;
 
        // FInd the next greater element
        // to the left
        while (l >= 0) {
 
            if (A.get(idx) > A.get(l)) {
                --l;
            }
            else {
                break;
            }
        }
 
        if (l < 0 || l == idx) {
            l = -2;
        }
 
        // Find the next greater element
        // to the right
        while (r < A.size()) {
            if (A.get(idx) > A.get(r)) {
                ++r;
            }
            else {
                break;
            }
        }
 
        if (r >= A.size() || r == idx) {
            r = -2;
        }
 
        // Return l and r in the form of
        // array of size 2
        return new ArrayList<Integer>(List.of(l, r));
    }
 
    // Function to find the minimum jumps
    // required to reach to all elements from
    // the largest element
    public static ArrayList<Integer> minJumps(int N, ArrayList<Integer> A)
    {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for(int i = 0 ; i < N ; i++){
            ans.add(0);
        }
 
        // Stores the mapping from index
        // to the element in array A[]
        TreeMap<Integer, ArrayList<Integer>> mp = new TreeMap<Integer, ArrayList<Integer>>();
 
        TreeMap<Integer, Integer> iToA = new TreeMap<Integer, Integer>();
        TreeMap<Integer, Integer> AToi = new TreeMap<Integer, Integer>();
 
        // Stores largest array element
        int big = A.get(0);
 
        // Find the two indices l, r such
        // that A[l] > A[i] < A[r] and
        // l<i<r using expand function
        for (int i = 0 ; i < N ; ++i) {
            big = Math.max(big, A.get(i));
            mp.put(i, expand(i, A));
 
            iToA.put(i, A.get(i));
            AToi.put(A.get(i), i);
        }
 
        // sorting A in descending order
        Collections.sort(A);
        Collections.reverse(A);
 
        for (int i = 0 ; i < A.size() ; ++i) {
 
            // Stores the resultant minimum
            // jumps required
            int m = 0;
 
            // Check if the current element
            // is largest or not
            if (A.get(i) == big) {
                int cur = AToi.get(A.get(i));
                ans.set(cur, 0);
                continue;
            }
 
            // Find the answer to the
            // current element
            int cur = AToi.get(A.get(i));
            int l = mp.get(cur).get(0);
            int r = mp.get(cur).get(1);
 
            if (l >= 0 && r < N) {
                m = Math.min(ans.get(l), ans.get(r)) + 1;
            }
            else if (l < 0 && r < N) {
                m = ans.get(r) + 1;
            }
            else if (l >= 0 && r >= N) {
                m = ans.get(l) + 1;
            }
 
            // Update the resultant minimum
            // jumps for the current element
            ans.set(cur, m);
        }
 
        // Return the result
        return ans;
    }
 
 
    // Driver code
    public static void main(String args[])
    {
        ArrayList<Integer> arr = new ArrayList<Integer>(List.of(
            5, 1, 3, 4, 7
        ));
        int N = arr.size();
 
        ArrayList<Integer> out = minJumps(N, arr);
 
        // Print the result
        for(int i = 0 ; i < out.size() ; i++){
            System.out.print(out.get(i) + " ");
        }
        System.out.println("");
    }
}
 
// This code is contributed by subhamgoyal2014.

Python3

# Python program for the above approach
 
# Function to find next greater element
# to left and right of current element
def expand(idx, A):
 
    # Starting l and r from previous
    # and the next element of the
    # current element
    l = idx - 1
    r = idx + 1
 
    # FInd the next greater element
    # to the left
    while (l >= 0):
        if (A[idx] > A[l]):
          l -= 1
        else:
          break
 
    if (l < 0 or l == idx):
        l = -2
 
    # Find the next greater element
    # to the right
    while (r < len(A)):
        if (A[idx] > A[r]):
            r += 1
        else:
            break
 
    if (r >= len(A) or r == idx):
        r = -2
 
    # Return l and r in the form of
    # array of size 2
    return [l, r]
 
 
# Function to find the minimum jumps
# required to reach to all elements from
# the largest element
def minJumps(N, A):
    ans = [0 for i in range(N)]
 
    # Stores the mapping from index
    # to the element in array A[]
    mp = {}
 
    iToA = {}
    AToi = {}
 
    # Stores largest array element
    big = A[0]
 
    # Find the two indices l, r such
    # that A[l] > A[i] < A[r] and
    # l<i<r using expand function
    for i in range(N):
        big = max(big, A[i])
        mp[i] = expand(i, A)
 
        iToA[i] = A[i]
        AToi[A[i]] = i
 
    # sorting A in descending order
    A = sorted(A, reverse=True)
 
    for i in range(len(A)):
        # Stores the resultant minimum
        # jumps required
        m = None
 
        # Check if the current element
        # is largest or not
        if (A[i] == big):
            cur = AToi[A[i]]
            ans[cur] = 0
            continue
 
        # Find the answer to the
        # current element
        cur = AToi[A[i]]
        l = mp[cur][0]
        r = mp[cur][1]
 
        if (l >= 0 and r < N):
            m = min(ans[l], ans[r]) + 1
        elif (l < 0 and r < N):
            m = ans[r] + 1
        elif (l >= 0 and r >= N):
            m = ans[l] + 1
 
        # Update the resultant minimum
        # jumps for the current element
        ans[cur] = m
 
    # Return the result
    return ans
 
# Driver Code
arr = [5, 1, 3, 4, 7]
N = len(arr)
 
out = minJumps(N, arr)
 
# Print the result
for it in out:
    print(it, end=" ")
 
    # This code is contributed by saurabh_jaiswal.

C#

using System;
using System.Collections.Generic;
 
class GFG 
{
 
  // Function to find next greater element
  // to left and right of current element
  public static List<int> Expand(int idx, List<int> A)
  {
 
    // Starting l and r from previous
    // and the next element of the
    // current element
    int l = idx - 1;
    int r = idx + 1;
 
    // Find the next greater element
    // to the left
    while (l >= 0) {
      if (A[idx] > A[l]) {
        --l;
      }
      else {
        break;
      }
    }
 
    if (l < 0 || l == idx) {
      l = -2;
    }
 
    // Find the next greater element
    // to the right
    while (r < A.Count) {
      if (A[idx] > A[r]) {
        ++r;
      }
      else {
        break;
      }
    }
 
    if (r >= A.Count || r == idx) {
      r = -2;
    }
 
    // Return l and r in the form of
    // array of size 2
    return new List<int>{ l, r };
  }
 
  // Function to find the minimum jumps
  // required to reach to all elements from
  // the largest element
  public static List<int> MinJumps(int N, List<int> A)
  {
    List<int> ans = new List<int>();
    for (int i = 0; i < N; i++) {
      ans.Add(0);
    }
 
    // Stores the mapping from index
    // to the element in array A[]
    SortedDictionary<int, List<int> > mp
      = new SortedDictionary<int, List<int> >();
 
    SortedDictionary<int, int> iToA
      = new SortedDictionary<int, int>();
    SortedDictionary<int, int> AToi
      = new SortedDictionary<int, int>();
 
    // Stores largest array element
    int big = A[0];
 
    // Find the two indices l, r such
    // that A[l] > A[i] < A[r] and
    // l<i<r using expand function
    for (int i = 0; i < N; ++i) {
      big = Math.Max(big, A[i]);
      mp.Add(i, Expand(i, A));
 
      iToA.Add(i, A[i]);
      AToi.Add(A[i], i);
    }
 
    // sorting A in descending order
    A.Sort();
    A.Reverse();
 
    for (int i = 0; i < A.Count; ++i) {
      // Stores the resultant minimum
      // jumps required
      int m = 0;
 
      // Check if the current element
      // is largest or not
      if (A[i] == big) {
        int cur = AToi[A[i]];
        ans[cur] = 0;
        continue;
      }
 
      // Find the answer to the
      // current element
      int curs = AToi[A[i]];
      int l = mp[curs][0];
      int r = mp[curs][1];
 
      if (l >= 0 && r < N) {
        m = Math.Min(ans[l], ans[r]) + 1;
      }
      else if (l < 0 && r < N) {
        m = ans[r] + 1;
      }
      else if (l >= 0 && r >= N) {
        m = ans[l] + 1;
      }
 
      // Update the resultant minimum
      // jumps for the current element
      ans[curs] = m;
    }
 
    // Return the result
    return ans;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    List<int> arr = new List<int>{ 5, 1, 3, 4, 7 };
    int N = arr.Count;
 
    List<int> outs = MinJumps(N, arr);
 
    // Print the result
    for (int i = 0; i < outs.Count; i++) {
      Console.Write(outs[i] + " ");
    }
    Console.WriteLine(" ");
  }
}
 
// This code is contributed by phasing17.

Javascript

<script>
// Javascript program for the above approach
 
// Function to find next greater element
// to left and right of current element
function expand(idx, A)
{
 
  // Starting l and r from previous
  // and the next element of the
  // current element
  let l = idx - 1;
  let r = idx + 1;
 
  // FInd the next greater element
  // to the left
  while (l >= 0) {
    if (A[idx] > A[l]) {
      --l;
    } else {
      break;
    }
  }
 
  if (l < 0 || l == idx) {
    l = -2;
  }
 
  // Find the next greater element
  // to the right
  while (r < A.length) {
    if (A[idx] > A[r]) {
      ++r;
    } else {
      break;
    }
  }
 
  if (r >= A.length || r == idx) {
    r = -2;
  }
 
  // Return l and r in the form of
  // array of size 2
  return [l, r];
}
 
// Function to find the minimum jumps
// required to reach to all elements from
// the largest element
function minJumps(N, A) {
  let ans = new Array(N).fill(0);
 
  // Stores the mapping from index
  // to the element in array A[]
  let mp = new Map();
 
  let iToA = new Map();
  let AToi = new Map();
 
  // Stores largest array element
  let big = A[0];
 
  // Find the two indices l, r such
  // that A[l] > A[i] < A[r] and
  // l<i<r using expand function
  for (let i = 0; i < N; ++i) {
    big = Math.max(big, A[i]);
    mp.set(i, expand(i, A));
 
    iToA.set(i, A[i]);
    AToi.set(A[i], i);
  }
 
  // sorting A in descending order
  A.sort((a, b) => - a + b);
 
  for (let i = 0; i < A.length; ++i) {
    // Stores the resultant minimum
    // jumps required
    let m;
 
    // Check if the current element
    // is largest or not
    if (A[i] == big) {
      let cur = AToi.get(A[i]);
      ans[cur] = 0;
      continue;
    }
 
    // Find the answer to the
    // current element
    let cur = AToi.get(A[i]);
    let l = mp.get(cur)[0];
    let r = mp.get(cur)[1];
 
    if (l >= 0 && r < N) {
      m = Math.min(ans[l], ans[r]) + 1;
    } else if (l < 0 && r < N) {
      m = ans[r] + 1;
    } else if (l >= 0 && r >= N) {
      m = ans[l] + 1;
    }
 
    // Update the resultant minimum
    // jumps for the current element
    ans[cur] = m;
  }
 
  // Return the result
  return ans;
}
 
// Driver Code
 
let arr = [5, 1, 3, 4, 7];
let N = arr.length;
 
let out = minJumps(N, arr);
 
// Print the result
for (it of out) document.write(it + " ");
 
// This code is contributed by gfgking.
</script>

Output:

1 2 2 1 0

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 zambiatek!