Next Greater Frequency Element

Optimise Approach - 1

This problem can be solved by the use of simple hashing and stack data structure.Hash will store the key value pair as the value of the element and its corresponding frequency.Stack will be used to store the position of the elements in the given array.

Algorithm

Step 1: Create a list to store the frequency of the element by using element value as the index  frequency as its value.

Step 2: Initialize a stack and push the position of the first element of the array.

Step 3: Iterate over rest of the positions of the array and do the following:

1. Check if the frequency of the current element is lesser than that of the element pointed by the top of stack,then push the current elements index to the stack.
2. If the frequency of the current element is greater than the element pointed by the top of the stack,then :
3. Continue popping from the stack.
4. If the condition in step 3 fails,push the current elements index to the stack. 

Step 4: After the loop is over,pop every item from the stack and print -1 for them as their next greater frequency element does not exist.

Implementation

Code in C++

#include <bits/stdc++.h>
using namespace std;

//function to print the next greater frequency element for each element.
void nextGreaterFreqElement(int arr[],int size,int freq[]){
    //stack initialization
    stack<int> st;
    //pushing first index to the stack
    st.push(0);
    //resulting array
    int res[size];
    int i;
    
    for(i = 1;i<size;i++){
        // if the frequency of the current element is lesser than that of the element pointed by the top of stack,then push the current elements index to the stack.
        if(freq[arr[s.top()]] > freq[arr[i]]){
            st.push(i);
        }
        //If the frequency of the current element is greater than the element pointed by the top of the stack
        else{
            //popping from the stack till condition in step 3 fails
            while(!st.empty() && freq[arr[s.top()]] < freq[arr[i]]){
                res[st.top()] = arr[i];
                st.pop();
            }
            st.push(i);
        }
    }
    //printing the resultant array
    for(i = 0;i<size;i++){
        cout<<res[i]<<" ";
    }
}
//main function
int main(){
    //sample array
    int arr[] = { 5,6,6,7,8,5,6 };
    int size = 7;
    int mx = INT_MAX;
    //initialization of frequency list
    int freq[mx] = {0};
    //calculating the frequency of each element
    for(int i = 0;i<size;i++){
        freq[arr[i]]++;
    }
    //calling the function
    nextGreaterFreqElement(arr,size,freq);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

{ 6,-1,-1,5,5,6,-1 }

Complexity Analysis

Time Complexity: O(n)

Since the approach consists of traversal which is of the order O(n).Therefore overall time complexity would be of order O(n).

Space Complexity: O(n)

As the approach uses a stack and a list both of size n, therefore space complexity would be of order O(n)

Optimise Approach - 2

In this approach, instead of using a list, a hash map will be used in order to reduce the space consumption. Again, Hash will store the key value pair as the value of the element and its corresponding frequency. Stack will be used to store the position of the elements in the given array.

Algorithm

Step 1: Create a hashmap with key as element and value as the frequency.

Step 2: Iterate the array and store the frequency of each element in the map.

Step 3: create a resultant array res to store the result.

Step 4: Initiate the res[size-1] = -1 and push the end element along with its frequency into the stack.

Step 5: Iterate through the array in reverse and do the following:

1. If the frequency of the current element is greater than the element pointed by the top of the stack,then continue popping the stack till the condition fails.
2. If the stack is empty then place -1 in the resultant array.
3. If the stack is not empty then that means the top of the stack has higher frequency.Put it in the resultant array as the next greater frequency element.
4. Push the element along with its frequency.

Implementation

Code in C++

#include <bits/stdc++.h>
using namespace std;

stack<pair<int,int>> st;
map<int, int> mp;

void nextGreaterFreqElement(int arr[],int size){
    //creating a result array
    int res[size];
    int i;
    //populating the frequency count map
    for(i = 0;i<size;i++){
        mp[arr[i]]++;
    }
    st.push({arr[size-1],mp[arr[size-1]]});
    int freq;
    res[size-1] = -1;
    for(i = size-2;i>=0;i--){
        freq = mp[arr[i]];
        //If the frequency of the current element is greater than the element pointed by the top of the stack,then continue popping the stack till the condition fails
        while(!st.empty() && freq > st.top().second){
            st.pop();
        }
        res[i] = (st.size() == 0) ? -1 : st.top().first;
        st.push({arr[i],mp[arr[i]]});
    }
    for(i = 0;i<size;i++)
    cout<<res[i]<<" ";
}
int main(){
    //sample array
    int arr[] = { 5,6,6,7,8,5,6 };
    int size = 7;
    //calling the function to print next greater frequency element
    nextGreaterFreqElement(arr,size);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

{ 6,-1,-1,5,5,6,-1 }

You can also try this code with Online C++ Compiler

Run Code

Complexity Analysis

Time Complexity: O(n)

Since the approach consists of traversal which is of the order O(n).Therefore overall time complexity would be of order O(n).

Space Complexity: O(n)

Worst case complexity would be of order of n when all the elements will be distinct.

Must Read Stack Operations

Frequently Asked Questions

What is a stack?

A stack is a linear data structure which comprises homogeneous elements and works on the principle of last in first out. That means, one which goes in last will come out first.

What is the greedy approach? 

It is an algorithm to get the optimal solution for the problem. In this algorithm, we always choose the next best solution that seems optimal at that step. We build solutions piece by piece to reach the optimal solution.

What is a map?

A map is like a dictionary where elements are stored in key-value manner. It stores the elements in the sorted order of keys.

What is the time complexity of push and pop operations in stack?

The time complexity of push and pop operations is O(1) since it takes a constant amount of time to either push an element in the top or pop the top element and reduce size by one.

Conclusion

This article discussed the approach to find the next greater frequency element for each element in the array.First a list and stack based solution is discussed.Later a space optimised approach is discussed.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!