Given an array of N integers and Q queries, print the number of next greater elements to the right of the given index element.
Examples:
Input: a[] = {3, 4, 2, 7, 5, 8, 10, 6}
q = 2
index = 0, index = 5Output: 6, 1
Explanation: The next greater elements to the right of 3(index 0) are 4,7,5,8,10,6.
The next greater elements to the right of 8(index 5) are 10.
Naive Approach: To solve the problem follow the below idea:
Iterate for every query from index to end and find out the number of next greater elements to the right
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find number of next// greater elements on the right of// a given elementint nextGreaterElements(vector<int>& a, int index){ int count = 0, N = a.size(); for (int i = index + 1; i < N; i++) if (a[i] > a[index]) count++; return count;}// Driver's codeint main(){ vector<int> a = { 3, 4, 2, 7, 5, 8, 10, 6 }; int Q = 2; vector<int> queries = { 0, 5 }; for (int i = 0; i < Q; i++) // Function call cout << nextGreaterElements(a, queries[i]) << " "; return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to find number of next greater elements on // the right of a given element static int nextGreaterElements(int[] a, int index) { int count = 0, N = a.length; for (int i = index + 1; i < N; i++) { if (a[i] > a[index]) { count++; } } return count; } public static void main(String[] args) { int[] a = { 3, 4, 2, 7, 5, 8, 10, 6 }; int Q = 2; int[] queries = { 0, 5 }; for (int i = 0; i < Q; i++) { // Function call System.out.print( nextGreaterElements(a, queries[i]) + " "); } }}// This code is contributed by lokeshmvs21. |
Python3
class GFG: # Function to find number of next greater elements on # the right of a given element @staticmethod def nextGreaterElements(a, index): count = 0 N = len(a) i = index + 1 while (i < N): if (a[i] > a[index]): count += 1 i += 1 return count @staticmethod def main(args): a = [3, 4, 2, 7, 5, 8, 10, 6] Q = 2 queries = [0, 5] i = 0 while (i < Q): # Function call print(str(GFG.nextGreaterElements(a, queries[i])) + " ", end="") i += 1if __name__ == "__main__": GFG.main([]) |
C#
// C# code for the above approachusing System;public class GFG { // Function to find number of next greater elements on // the right of a given element static int nextGreaterElements(int[] a, int index) { int count = 0, N = a.Length; for (int i = index + 1; i < N; i++) { if (a[i] > a[index]) { count++; } } return count; } static public void Main() { // Code int[] a = { 3, 4, 2, 7, 5, 8, 10, 6 }; int Q = 2; int[] queries = { 0, 5 }; for (int i = 0; i < Q; i++) { // Function call Console.Write(nextGreaterElements(a, queries[i]) + " "); } }}// This code is contributed by lokeshmvs21. |
Javascript
// Function to find number of next greater elements on // the right of a given element function nextGreaterElements(a, index) { var count = 0; var N = a.length; var i=0; for (i; i < N; i++) { if (a[i] > a[index]) { count++; } } return count; } var a = [3, 4, 2, 7, 5, 8, 10, 6]; var Q = 2; var queries = [0, 5]; var i =0; for (i; i < Q; i++) { // Function call console.log(nextGreaterElements(a, queries[i]) + " "); }// This code is contributed by sourabhdalal0001. |
Output
6 1
Time Complexity: O(NQ), and O(N) to answer a single query
Auxiliary space: O(1)
Optimized Approach
The idea behind this approach is Count Inversion(Merge Sort). In Count Inversion we were finding Inversion pair using merge sort. For i<j if arr[i]>arr[j] then that will be an inversion pair. Using similar logic we can find those pair for which i<j and arr[i]<arr[j]. So we can find, there are how many “j” for an “i” such that i<j and arr[i]<arr[j]. Then that number of j will be the number of the next greater element for i.
So we will simply perform merge sort and in merging we will check this condition -” i<j and arr[i]<arr[j]”
Algorithm:
- Declare a vector “ans” to store the Number of NGEs to the right for every element
- We will use a vector of pair to store the element along with their index
- In the pair, the first element will be the number and the second element will be the index of that number
- Sort the vector of pair on the basis of the first element of the pair
- Used vector of pair because after sorting, the position of the element will change but every element has its previous index so that we can track its previous position.
- So we will find the number of NGEs to the right and store them in “ans” vector at the element’s previous position
- We will perform mergesort by calling mergesort recursively for the first half then for the second half and then calling the merge function
- In the merge function when any element let us say “a” of the first part is lesser than any other element of the second part let us say “b” then that element “a” of the first part will be smaller than those elements of the second part which are from “b” till last.
- In other words, all those elements from “b” till last will be the next greater element for “a“
- So, find the count of all the elements in the second part from “b” till the last.
- Then add that count in “ans” vector at a’s position
- In last we have the Number of next greater element for each index, so return NGEs for those indexes which are given in the query
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function for performing merge operationvoid merge(vector<pair<int, int> >& vec, vector<int>& ans, int low, int mid, int high){ int n1 = mid - low + 1; int n2 = high - mid; vector<pair<int, int> > arr; vector<pair<int, int> > brr; for (int i = 0; i < n1; i++) { arr.push_back(vec[i + low]); } for (int i = 0; i < n2; i++) { brr.push_back(vec[i + mid + 1]); } int i = 0; int j = 0; int k = low; while (i < n1 && j < n2) { if (arr[i].first < brr[j].first) { // Finding Number of next greater element ans[arr[i].second] += n2 - j; vec[k] = arr[i]; i++; k++; } else { vec[k] = brr[j]; j++; k++; } } while (i < n1) { vec[k] = arr[i]; i++; k++; } while (j < n2) { vec[k] = brr[j]; j++; k++; }}// Function for performing Merge Sortvoid mergesort(vector<pair<int, int> >& vec, vector<int>& ans, int low, int high){ int mid; if (low < high) { // Divide them into two different part mid = low + (high - low) / 2; // Calling mergesort function recursively for both // the part mergesort(vec, ans, low, mid); mergesort(vec, ans, mid + 1, high); // Merging both and part and calculating Number of // Next greater element merge(vec, ans, low, mid, high); }}// Function to find number of next// greater elements on the right of// a given elementvoid nextGreaterElements(int n, vector<int>& nums, int queries, vector<int>& indices){ // Storing elements of vector with their index into // vector of pair vector<pair<int, int> > vec; for (int i = 0; i < n; i++) { vec.push_back({ nums[i], i }); } // Declaring a vector to store Number of next greater // element for every element vector<int> ans(n, 0); mergesort(vec, ans, 0, n - 1); // Printing number of next greater element for Q queries for (int i = 0; i < queries; i++) { int j = indices[i]; cout << ans[j] << " "; }}// Driver's codeint main(){ vector<int> nums = { 3, 4, 2, 7, 5, 8, 10, 6 }; int queries = 2; vector<int> indices = { 0, 5 }; // Function call nextGreaterElements(nums.size(), nums, queries, indices); return 0;} |
Java
// java code for the above approachimport java.io.*;import java.util.*;public class GFG { // Function for performing merge operation static void merge(List<Pair<Integer, Integer>> vec, int[] ans, int low, int mid, int high) { int n1 = mid - low + 1; int n2 = high - mid; List<Pair<Integer, Integer>> arr = new ArrayList<>(); List<Pair<Integer, Integer>> brr = new ArrayList<>(); // Copy elements to temporary arrays for (int i = 0; i < n1; i++) { arr.add(vec.get(i + low)); } for (int i = 0; i < n2; i++) { brr.add(vec.get(i + mid + 1)); } int i = 0; int j = 0; int k = low; while (i < n1 && j < n2) { if (arr.get(i).first < brr.get(j).first) { // Finding number of next greater elements ans[arr.get(i).second] += n2 - j; vec.set(k, arr.get(i)); i++; k++; } else { vec.set(k, brr.get(j)); j++; k++; } } while (i < n1) { vec.set(k, arr.get(i)); i++; k++; } while (j < n2) { vec.set(k, brr.get(j)); j++; k++; } } // Function for performing Merge Sort static void mergeSort(List<Pair<Integer, Integer>> vec, int[] ans, int low, int high) { int mid; if (low < high) { // Divide them into two different parts mid = low + (high - low) / 2; // Calling mergeSort function recursively for both // the parts mergeSort(vec, ans, low, mid); mergeSort(vec, ans, mid + 1, high); merge(vec, ans, low, mid, high); } } // Function to find number of next greater elements on the right of // a given element static void nextGreaterElements(int n, int[] nums, int queries, int[] indices) { // Storing elements of the array with their index into // a list of pairs List<Pair<Integer, Integer>> vec = new ArrayList<>(); for (int i = 0; i < n; i++) { vec.add(new Pair<>(nums[i], i)); } // Declaring an array to store the number of next greater // elements for every element int[] ans = new int[n]; mergeSort(vec, ans, 0, n - 1); // Printing the number of next // greater elements for Q queries for (int i = 0; i < queries; i++) { int j = indices[i]; System.out.print(ans[j] + " "); } } // Driver's code public static void main(String[] args) { int[] nums = { 3, 4, 2, 7, 5, 8, 10, 6 }; int queries = 2; int[] indices = { 0, 5 }; // Function call nextGreaterElements(nums.length, nums, queries, indices); } // Helper class to store pairs static class Pair<K, V> { K first; V second; Pair(K first, V second) { this.first = first; this.second = second; } }} |
Python3
# Function for performing merge operationdef merge(vec, ans, low, mid, high): n1 = mid - low + 1 n2 = high - mid arr = vec[low:low + n1] brr = vec[mid + 1:mid + 1 + n2] i = 0 j = 0 k = low while i < n1 and j < n2: if arr[i][0] < brr[j][0]: # Finding Number of next greater element ans[arr[i][1]] += n2 - j vec[k] = arr[i] i += 1 k += 1 else: vec[k] = brr[j] j += 1 k += 1 while i < n1: vec[k] = arr[i] i += 1 k += 1 while j < n2: vec[k] = brr[j] j += 1 k += 1# Function for performing Merge Sortdef mergesort(vec, ans, low, high): if low < high: # Divide them into two different part mid = low + (high - low) // 2 # Calling mergesort function recursively for both # the part mergesort(vec, ans, low, mid) mergesort(vec, ans, mid + 1, high) # Merging both and part and calculating Number of # Next greater element merge(vec, ans, low, mid, high)# Function to find number of next# greater elements on the right of# a given elementdef nextGreaterElements(n, nums, queries, indices): # Storing elements of list with their index into # list of pairs vec = [(nums[i], i) for i in range(n)] # Declaring a list to store Number of next greater # element for every element ans = [0] * n mergesort(vec, ans, 0, n - 1) # Printing number of next greater element for Q queries for i in indices: j = i print(ans[j], end=" ")# Driver's codeif __name__ == "__main__": nums = [3, 4, 2, 7, 5, 8, 10, 6] queries = 2 indices = [0, 5] # Function call nextGreaterElements(len(nums), nums, queries, indices) |
C#
using System;using System.Collections.Generic;class GFG { // Function for performing merge operation static void Merge(List<Tuple<int, int> > list, List<int> ans, int low, int mid, int high) { int n1 = mid - low + 1; int n2 = high - mid; List<Tuple<int, int> > leftArr = new List<Tuple<int, int> >(); List<Tuple<int, int> > rightArr = new List<Tuple<int, int> >(); for (int x = 0; x < n1; x++) { leftArr.Add(list[x + low]); } for (int y = 0; y < n2; y++) { rightArr.Add(list[y + mid + 1]); } int i = 0; int j = 0; int k = low; while (i < n1 && j < n2) { if (leftArr[i].Item1 < rightArr[j].Item1) { // Finding the number of next greater // elements ans[leftArr[i].Item2] += n2 - j; list[k] = leftArr[i]; i++; k++; } else { list[k] = rightArr[j]; j++; k++; } } while (i < n1) { list[k] = leftArr[i]; i++; k++; } while (j < n2) { list[k] = rightArr[j]; j++; k++; } } // Function for performing Merge Sort static void MergeSort(List<Tuple<int, int> > list, List<int> ans, int low, int high) { if (low < high) { int mid = low + (high - low) / 2; // Calling MergeSort function recursively for // both parts MergeSort(list, ans, low, mid); MergeSort(list, ans, mid + 1, high); // Merging both parts and calculating the number // of next greater elements Merge(list, ans, low, mid, high); } } // Function to find the number of next greater elements // on the right of a given element static void NextGreaterElements(int n, List<int> nums, int queries, List<int> indices) { // Storing elements of the list with their index // into a list of tuples List<Tuple<int, int> > list = new List<Tuple<int, int> >(); for (int i = 0; i < n; i++) { list.Add(new Tuple<int, int>(nums[i], i)); } // Declaring a list to store the number of next // greater elements for every element List<int> ans = new List<int>(new int[n]); MergeSort(list, ans, 0, n - 1); // Printing the number of next greater elements for // Q queries for (int j = 0; j < queries; j++) { int k = indices[j]; Console.Write(ans[k] + " "); } } // Driver's code static void Main() { List<int> nums = new List<int>{ 3, 4, 2, 7, 5, 8, 10, 6 }; int queries = 2; List<int> indices = new List<int>{ 0, 5 }; // Function call NextGreaterElements(nums.Count, nums, queries, indices); }} |
Javascript
// Function for performing merge operationfunction merge(vec, ans, low, mid, high) { let n1 = mid - low + 1; let n2 = high - mid; let arr = []; let brr = []; // Copy elements to temporary arrays for (let i = 0; i < n1; i++) { arr.push(vec[i + low]); } for (let i = 0; i < n2; i++) { brr.push(vec[i + mid + 1]); } let i = 0; let j = 0; let k = low; while (i < n1 && j < n2) { if (arr[i].first < brr[j].first) { // Finding number of next greater elements ans[arr[i].second] += n2 - j; vec[k] = arr[i]; i++; k++; } else { vec[k] = brr[j]; j++; k++; } } while (i < n1) { vec[k] = arr[i]; i++; k++; } while (j < n2) { vec[k] = brr[j]; j++; k++; }}// Function for performing Merge Sortfunction mergeSort(vec, ans, low, high) { if (low < high) { // Divide them into two different parts let mid = Math.floor(low + (high - low) / 2); // Calling mergeSort function recursively for both // the parts mergeSort(vec, ans, low, mid); mergeSort(vec, ans, mid + 1, high); merge(vec, ans, low, mid, high); }}// Function to find number of next greater elements on the right of// a given elementfunction nextGreaterElements(n, nums, queries, indices) { // Storing elements of the array with their index into // a list of pairs let vec = []; for (let i = 0; i < n; i++) { vec.push({ first: nums[i], second: i }); } // Declaring an array to store the number of next greater // elements for every element let ans = new Array(n).fill(0); mergeSort(vec, ans, 0, n - 1); // Printing the number of next greater elements for Q queries for (let i = 0; i < queries; i++) { let j = indices[i]; process.stdout.write(ans[j] + " "); }}// Driver's codelet nums = [3, 4, 2, 7, 5, 8, 10, 6];let queries = 2;let indices = [0, 5];// Function callnextGreaterElements(nums.length, nums, queries, indices);// Helper class to store pairsfunction Pair(first, second) { this.first = first; this.second = second;} |
Output-
6 1
Time Complexity: O(NlogN), because of Merge sort implementation
Auxiliary space: O(N)
Recommended
Solve DSA problems on GfG Practice.
Solve Problems
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!
