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 ith element to the jth 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 ith and jth 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 ith 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 elementar<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 elementvector<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 Codeint 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 approachclass 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 elementdef 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 elementdef 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 Codearr = [5, 1, 3, 4, 7]N = len(arr)out = minJumps(N, arr)# Print the resultfor 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 elementfunction 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 elementfunction 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 Codelet arr = [5, 1, 3, 4, 7];let N = arr.length;let out = minJumps(N, arr);// Print the resultfor (it of out) document.write(it + " ");// This code is contributed by gfgking.</script> |
Output:
1 2 2 1 0
Time Complexity: O(N2)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
