Next Greater Frequency Element
Last Updated :
14 Dec, 2023
Given an array, for each element find the value of the nearest element to the right which is having a frequency greater than that of the current element. If there does not exist an answer for a position, then make the value ‘-1’.
Examples:
Input : a[] = [1, 1, 2, 3, 4, 2, 1]
Output : [-1, -1, 1, 2, 2, 1, -1]
Explanation:
Given array a[] = [1, 1, 2, 3, 4, 2, 1]
Frequency of each element is: 3, 3, 2, 1, 1, 2, 3
Lets calls Next Greater Frequency element as NGF
1. For element a[0] = 1 which has a frequency = 3,
As it has frequency of 3 and no other next element
has frequency more than 3 so '-1'
2. For element a[1] = 1 it will be -1 same logic
like a[0]
3. For element a[2] = 2 which has frequency = 2,
NGF element is 1 at position = 6 with frequency
of 3 > 2
4. For element a[3] = 3 which has frequency = 1,
NGF element is 2 at position = 5 with frequency
of 2 > 1
5. For element a[4] = 4 which has frequency = 1,
NGF element is 2 at position = 5 with frequency
of 2 > 1
6. For element a[5] = 2 which has frequency = 2,
NGF element is 1 at position = 6 with frequency
of 3 > 2
7. For element a[6] = 1 there is no element to its
right, hence -1
Input : a[] = [1, 1, 1, 2, 2, 2, 2, 11, 3, 3]
Output : [2, 2, 2, -1, -1, -1, -1, 3, -1, -1]
Naive approach:
A simple hashing technique is to use values as the index is being used to store the frequency of each element. Create a list suppose to store the frequency of each number in the array. (Single traversal is required). Now use two loops.
The outer loop picks all the elements one by one.
The inner loop looks for the first element whose frequency is greater than the frequency of the current element.
If a greater frequency element is found then that element is printed, otherwise -1 is printed.
Time complexity: O(n*n)
Efficient approach:
We can use hashing and stack data structure to efficiently solve for many cases. A simple hashing technique is to use values as index and frequency of each element as value. We use the stack data structure to store the position of elements in the array.
- Create a list to use values as index to store frequency of each element.
- Push the position of first element to stack.
- Pick rest of the position of elements one by one and follow following steps in loop.
- Mark the position of current element as ‘i’ .
- If the frequency of the element which is pointed by the top of stack is greater than frequency of the current element, push the current position i to the stack
- If the frequency of the element which is pointed by the top of stack is less than frequency of the current element and the stack is not empty then follow these steps:
- continue popping the stack
- if the condition in step c fails then push the current position i to the stack
- After the loop in step 3 is over, pop all the elements from stack and print -1 as next greater frequency element for them does not exist.
Below is the implementation of the above problem.
C++
#include <iostream>
#include <stack>
#include <stdio.h>
using namespace std;
void NFG(int a[], int n, int freq[])
{
stack<int> s;
s.push(0);
int res[n] = { 0 };
for (int i = 1; i < n; i++)
{
if (freq[a[s.top()]] > freq[a[i]])
s.push(i);
else {
while ( !s.empty()
&& freq[a[s.top()]] < freq[a[i]])
{
res[s.top()] = a[i];
s.pop();
}
s.push(i);
}
}
while (!s.empty()) {
res[s.top()] = -1;
s.pop();
}
for (int i = 0; i < n; i++)
{
cout << res[i] << " ";
}
}
int main()
{
int a[] = { 1, 1, 2, 3, 4, 2, 1 };
int len = 7;
int max = INT16_MIN;
for (int i = 0; i < len; i++)
{
if (a[i] > max) {
max = a[i];
}
}
int freq[max + 1] = { 0 };
for (int i = 0; i < len; i++)
{
freq[a[i]]++;
}
NFG(a, len, freq);
return 0;
}
|
Java
import java.util.*;
class GFG {
static void NFG(int a[], int n, int freq[])
{
Stack<Integer> s = new Stack<Integer>();
s.push(0);
int res[] = new int[n];
for (int i = 0; i < n; i++)
res[i] = 0;
for (int i = 1; i < n; i++)
{
if (freq[a[s.peek()]] > freq[a[i]])
s.push(i);
else
{
while (freq[a[s.peek()]] < freq[a[i]]
&& s.size() > 0)
{
res[s.peek()] = a[i];
s.pop();
}
s.push(i);
}
}
while (s.size() > 0)
{
res[s.peek()] = -1;
s.pop();
}
for (int i = 0; i < n; i++)
{
System.out.print(res[i] + " ");
}
}
public static void main(String args[])
{
int a[] = { 1, 1, 2, 3, 4, 2, 1 };
int len = 7;
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
int freq[] = new int[max + 1];
for (int i = 0; i < max + 1; i++)
freq[i] = 0;
for (int i = 0; i < len; i++)
{
freq[a[i]]++;
}
NFG(a, len, freq);
}
}
|
Python3
def NFG(a, n):
if n <= 0:
print("List empty")
return []
stack = [0] * n
freq = {}
for i in a:
freq[i] = 0
for i in a:
freq[i] += 1
res = [0] * n
top = -1
top += 1
stack[top] = 0
for i in range(1, n):
if freq[a[stack[top]]] > freq[a[i]]:
top += 1
stack[top] = i
else:
while top > -1 and freq[a[stack[top]]] < freq[a[i]]:
res[stack[top]] = a[i]
top -= 1
top += 1
stack[top] = i
while top > -1:
res[stack[top]] = -1
top -= 1
return res
print(NFG([1, 1, 2, 3, 4, 2, 1], 7))
|
C#
using System;
using System.Collections;
class GFG {
static void NFG(int[] a, int n, int[] freq)
{
Stack s = new Stack();
s.Push(0);
int[] res = new int[n];
for (int i = 0; i < n; i++)
res[i] = 0;
for (int i = 1; i < n; i++)
{
if (freq[a[(int)s.Peek()]] > freq[a[i]])
s.Push(i);
else
{
while (freq[a[(int)(int)s.Peek()]]
< freq[a[i]]
&& s.Count > 0)
{
res[(int)s.Peek()] = a[i];
s.Pop();
}
s.Push(i);
}
}
while (s.Count > 0)
{
res[(int)s.Peek()] = -1;
s.Pop();
}
for (int i = 0; i < n; i++)
{
Console.Write(res[i] + " ");
}
}
public static void Main(String[] args)
{
int[] a = { 1, 1, 2, 3, 4, 2, 1 };
int len = 7;
int max = int.MinValue;
for (int i = 0; i < len; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
int[] freq = new int[max + 1];
for (int i = 0; i < max + 1; i++)
freq[i] = 0;
for (int i = 0; i < len; i++)
{
freq[a[i]]++;
}
NFG(a, len, freq);
}
}
|
Javascript
<script>
function NFG(a, n, freq)
{
let s = [];
s.push(0);
let res = new Array(n);
for (let i = 0; i < n; i++)
res[i] = 0;
for (let i = 1; i < n; i++)
{
if (freq[a[s[s.length - 1]]] > freq[a[i]])
s.push(i);
else
{
while (freq[a[s[s.length - 1]]]
< freq[a[i]]
&& s.length > 0)
{
res[s[s.length - 1]] = a[i];
s.pop();
}
s.push(i);
}
}
while (s.length > 0)
{
res[s[s.length - 1]] = -1;
s.pop();
}
document.write("[");
for (let i = 0; i < n - 1; i++)
{
document.write(res[i] + ", ");
}
document.write(res[n - 1] + "]");
}
let a = [ 1, 1, 2, 3, 4, 2, 1 ];
let len = 7;
let max = Number.MIN_VALUE;
for (let i = 0; i < len; i++)
{
if (a[i] > max)
{
max = a[i];
}
}
let freq = new Array(max + 1);
for (let i = 0; i < max + 1; i++)
freq[i] = 0;
for (let i = 0; i < len; i++)
{
freq[a[i]]++;
}
NFG(a, len, freq);
</script>
|
Time complexity: O(n)
Auxiliary space: O(n)
The Next To Brute Force/Brute Force:
The Approach:
The approach is simple we just store the frequency of all element in map then push all element in reverse order to the stack as we know the nature of stack is LIFO so then we traverse over vector and find the next greater for every element in vector using stack ans map.
C++
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
vector<int>v{1, 1, 2, 3, 4, 2, 1};
int n=v.size();
map<int,int>mp;
stack<int>s;
for(auto it:v){
mp[it]++;
}
for(int i=n-1;i>=0;i--)s.push(v[i]);
for(int i=0;i<n;i++){
int x=mp[v[i]];
bool flag=1;
stack<int>ss(s);
while(!ss.empty()){
if(mp[ss.top()]>x){
cout<<v[i]<<" --> "<<ss.top()<<endl;
flag=0;
break;
}
ss.pop();
}
if(flag)cout<<v[i]<<" --> "<<-1<<endl;
s.pop();
}
return 0;
}
|
Java
import java.util.*;
class Main {
public static void main(String[] args)
{
List<Integer> v
= Arrays.asList(1, 1, 2, 3, 4, 2, 1);
int n = v.size();
Map<Integer, Integer> mp = new HashMap<>();
Stack<Integer> s = new Stack<>();
for (int i : v) {
mp.put(i, mp.getOrDefault(i, 0) + 1);
}
for (int i = n - 1; i >= 0; i--)
s.push(v.get(i));
for (int i = 0; i < n; i++) {
int x = mp.get(v.get(i));
boolean flag = true;
Stack<Integer> ss = (Stack<Integer>)s.clone();
while (!ss.empty()) {
if (mp.get(ss.peek()) > x) {
System.out.println(v.get(i) + " --> "
+ ss.peek());
flag = false;
break;
}
ss.pop();
}
if (flag)
System.out.println(v.get(i) + " --> " + -1);
s.pop();
}
}
}
|
Python3
from collections import defaultdict
def main():
v = [1, 1, 2, 3, 4, 2, 1]
n = len(v)
mp = defaultdict(int)
s = []
for x in v:
mp[x] += 1
for i in range(n-1, -1, -1):
s.append(v[i])
for i in range(n):
x = mp[v[i]]
flag = True
ss = list(s)
while ss:
if mp[ss[-1]] > x:
print(v[i], "-->", ss[-1])
flag = False
break
ss.pop()
if flag:
print(v[i], "-->", -1)
s.pop()
if __name__ == "__main__":
main()
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG {
static void Main() {
int[] v = {1, 1, 2, 3, 4, 2, 1};
int n=v.Length;
Dictionary<int, int> mp = new Dictionary<int, int>();
Stack s = new Stack();
for(int i = 0; i < v.Length; i++){
if(mp.ContainsKey(v[i]) == true){
mp[v[i]] = mp[v[i]] + 1;
}
else{
mp.Add(v[i], 1);
}
}
for(int i=n-1;i>=0;i--){
s.Push(v[i]);
}
for(int i=0;i<n;i++){
int x = mp[v[i]];
int flag=1;
Stack ss = (Stack)s.Clone();
while(ss.Count > 0){
int val = (int)ss.Peek();
if(mp[val]>x){
Console.WriteLine(v[i] + " --> " + val);
flag=0;
break;
}
ss.Pop();
}
if(flag != 0){
Console.WriteLine(v[i] + " --> -1");
}
s.Pop();
}
}
}
|
Javascript
let v = [1, 1, 2, 3, 4, 2, 1];
let n=v.length;
let mp = new Map();
let s = [];
for (let i = 0; i < n; i++){
if(mp.has(v[i]))
mp.set(v[i], mp.get(v[i])+1)
else
mp.set(v[i], 1)
}
for(let i=n-1;i>=0;i--) s.push(v[i]);
for(let i=0; i < n; i++){
let x= mp.get(v[i]);
let flag=1;
let ss = new Array(s.length);
for(let i = 0; i < s.length; i++){
ss[i] = s[i];
}
while(ss.length > 0){
if(mp.get(ss[ss.length - 1]) > x){
document.write(v[i] + " --> " + ss[ss.length - 1]);
flag=0;
break;
}
ss.pop();
}
if(flag)document.write(v[i] + " --> " + -1);
s.pop();
}
|
Output
1 --> -1
1 --> -1
2 --> 1
3 --> 2
4 --> 2
2 --> 1
1 --> -1
Time complexity: O(n^2),for worst case.
Auxiliary space: O(2n),for map and stack.
Space Efficient Approach: using a hash map instead of a list as mentioned in the above approach.
Steps:
- Create a class pair to store pair<int, int> with pair<element, frequency>.
- Create a hash map with pair as generics to store keys as the element and values as the frequency of every element.
- Iterate the array and save the element and its frequency in the hashmap.
- Create a res array that stores the resultant array.
- Initially make res[n-1] = -1 and push the element in the end along with its frequency into the stack.
- Iterate through the array in reverse order.
- If the frequency of the element which is pointed at the top of the stack is less than the frequency of the current element and the stack is not empty then pop.
- Continue till the loop fails.
- If the stack is empty, it means that there is no element with a higher frequency. So, place -1 as the next higher frequency element in the resultant array.
- If the stack is not empty, it means that the top of the stack has a higher frequency element. Put it in the resultant array as the next higher frequency.
- Push the current element along with its frequency.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
stack<pair<int,int>> mystack;
map<int, int> mymap;
void NGF(int arr[], int res[], int n) {
for(int i = 0; i < n; i++) {
mymap[arr[i]] += 1;
}
int curr_freq = mymap[arr[n-1]];
mystack.push({arr[n-1], curr_freq});
res[n-1] = -1;
for(int i = n-2;i>=0;i--) {
curr_freq = mymap[arr[i]];
while(mystack.size() > 0 && curr_freq >= mystack.top().second)
mystack.pop();
res[i] = (mystack.size() == 0) ? -1 : mystack.top().first;
mystack.push({arr[i], mymap[arr[i]]});
}
}
int main()
{
int arr[] = {1, 1, 1, 2, 2, 2, 2, 11, 3, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int res[n];
NGF(arr, res, n);
cout << "[";
for(int i = 0; i < n - 1; i++)
{
cout << res[i] << ", ";
}
cout << res[n - 1] << "]";
return 0;
}
|
Java
import java.util.*;
class GFG {
Stack<Pair> mystack = new Stack<>();
HashMap<Integer,Integer> mymap = new HashMap<>();
class Pair{
int data;
int freq;
Pair(int data,int freq){
this.data = data;
this.freq = freq;
}
}
void NGF(int[] arr,int[] res) {
int n = arr.length;
for(int i = 0;i<n;i++) {
if(mymap.containsKey(arr[i]))
mymap.put(arr[i], mymap.get(arr[i]) + 1);
else
mymap.put(arr[i], 1);
}
int curr_freq = mymap.get(arr[n-1]);
mystack.push(new Pair(arr[n-1],curr_freq));
res[n-1] = -1;
for(int i = n-2;i>=0;i--) {
curr_freq = mymap.get(arr[i]);
while(!mystack.isEmpty() && curr_freq >= mystack.peek().freq)
mystack.pop();
res[i] = (mystack.isEmpty()) ? -1 : mystack.peek().data;
mystack.push(new Pair(arr[i],mymap.get(arr[i])));
}
}
public static void main(String args[]) {
GFG obj = new GFG();
int[] arr = {1, 1, 1, 2, 2, 2, 2, 11, 3, 3};
int res[] = new int[arr.length];
obj.NGF(arr, res);
System.out.println(Arrays.toString(res));
}
}
|
Python3
mystack = []
mymap = {}
def NGF(arr, res):
n = len(arr)
for i in range(n):
if arr[i] in mymap:
mymap[arr[i]] += 1
else:
mymap[arr[i]] = 1
curr_freq = mymap[arr[n-1]]
mystack.append([arr[n-1],curr_freq])
res[n-1] = -1
for i in range(n - 2, -1, -1):
curr_freq = mymap[arr[i]]
while len(mystack) > 0 and curr_freq >= mystack[-1][1]:
mystack.pop()
if (len(mystack) == 0):
res[i] = -1
else:
res[i] = mystack[-1][0]
mystack.append([arr[i],mymap[arr[i]]])
arr = [1, 1, 1, 2, 2, 2, 2, 11, 3, 3]
res = [0]*(len(arr))
NGF(arr, res)
print(res)
|
C#
using System;
using System.Collections.Generic;
class GFG {
static Stack<Tuple<int,int>> mystack = new Stack<Tuple<int,int>>();
static Dictionary<int, int> mymap = new Dictionary<int, int>();
static void NGF(int[] arr,int[] res) {
int n = arr.Length;
for(int i = 0; i < n; i++) {
if(mymap.ContainsKey(arr[i]))
mymap[arr[i]] = mymap[arr[i]] + 1;
else
mymap[arr[i]] = 1;
}
int curr_freq = mymap[arr[n-1]];
mystack.Push(new Tuple<int,int>(arr[n-1],curr_freq));
res[n-1] = -1;
for(int i = n-2;i>=0;i--) {
curr_freq = mymap[arr[i]];
while(mystack.Count > 0 && curr_freq >= mystack.Peek().Item2)
mystack.Pop();
res[i] = (mystack.Count == 0) ? -1 : mystack.Peek().Item1;
mystack.Push(new Tuple<int,int>(arr[i],mymap[arr[i]]));
}
}
static void Main() {
int[] arr = {1, 1, 1, 2, 2, 2, 2, 11, 3, 3};
int[] res = new int[arr.Length];
NGF(arr, res);
Console.Write("[");
for(int i = 0; i < arr.Length - 1; i++)
{
Console.Write(res[i] + ", ");
}
Console.Write(res[arr.Length - 1] + "]");
}
}
|
Javascript
<script>
class Pair
{
constructor(data,freq)
{
this.data = data;
this.freq = freq;
}
}
let mystack = [];
let mymap = new Map();
function NGF(arr,res)
{
let n = arr.length;
for(let i = 0;i<n;i++) {
if(mymap.has(arr[i]))
mymap.set(arr[i], mymap.get(arr[i]) + 1);
else
mymap.set(arr[i], 1);
}
let curr_freq = mymap.get(arr[n-1]);
mystack.push(new Pair(arr[n-1],curr_freq));
res[n-1] = -1;
for(let i = n - 2; i >= 0; i--)
{
curr_freq = mymap.get(arr[i]);
while(mystack.length!=0 && curr_freq >= mystack[mystack.length-1].freq)
mystack.pop();
res[i] = (mystack.length==0) ? -1 : mystack[mystack.length-1].data;
mystack.push(new Pair(arr[i],mymap.get(arr[i])));
}
}
let arr=[1, 1, 1, 2, 2, 2, 2, 11, 3, 3];
let res = new Array(arr.length);
NGF(arr, res);
document.write((res).join(" "));
</script>
|
Output
[2, 2, 2, -1, -1, -1, -1, 3, -1, -1]
Time Complexity: O(n)
Auxiliary Space: O(n) for hashmap and stack
Thank you Koustav for your valuable support.
Please Login to comment...