Next Greater Frequency Element

“Next Greater Frequency Element” is a standard problem of stack data structure. Here, in this problem, we are given an array and our task is to write a program to find the next (right side) greater frequency element of every element.

If for any particular element next greater frequency element is not present, then simply print ‘-1’ for that element.

Example:
 
Arr[] = [15, 13, 12, 15, 15, 13]
Here, 
Frequency of 15 = 3
Frequency of 13 = 2
Frequency of 12 = 1
So, Frequency Array = [3, 2, 1, 3, 3, 2]
The Next greater frequency element of every element will be:
[-1, 15, 15, -1, -1, -1]
 
Explanation:
 
For index = 0 and element = 15,
15 has highest frequency and there is no next greater frequency element present from index [1-5]. So, ‘-1’ will be the result.
 
For index = 1 and element = 13,
13 has second highest frequency with frequency as 2 and there is element ‘15’ which is present at index ‘3’. So, ‘15’ will be the next greater frequency element for element ‘13’ at index ‘1’.
 
For index = 2 and element = 12,
12 has lowest frequency with frequency as 1 and there is element ‘15’ which is present at index ‘3’. So, ‘15’ will be the next greater frequency element for element ‘12’ at index ‘2’.
 
For index = 3 and element = 15,
15 has highest frequency and there is no next greater frequency element present from index [4-5]. So, ‘-1’ will be the result.
 
For index = 4 and element = 15,
15 has highest frequency and there is no next greater frequency element present at index [5]. So, ‘-1’ will be the result.
 
For index = 5 and element = 13,
13 has second highest frequency with frequency as 2 and but there is no next greater frequency element for ‘13’ as ‘5’ is the last index of the array and there is nothing to search for after this element.

This problem seems to be simple at first, but we need to solve the given problem efficiently.

Here, in this post, I am going to discuss two methods to solve the given problem:

1. Brute – Force Method
2. Stack Based Approach

METHOD 1: Brute-Force Method

The steps required to find next greater frequency element of every element are as follows:

1. Create a temporary array freq[] and store the frequency of each element of original  in this temporary array.
2. Now, for every element of original array, scan the next index elements in the frequency array and find the next greater element of every element in original array.

For example, for array element arr[i], where ‘i’ is random index from 0 to ‘n-1’, scan the frequency array from ‘i+1’ to ‘n-1’ and find the first index, say ‘j’, where 

freq[j] is greater than freq[i] and return the arr[j] as result, which will be next greater frequency element for arr[i].

If there is no next greater frequency element present for the particular element in original array, then print ‘-1’.

The time complexity of this solution is 2*O(n²) ~ O(n²). First O(n²) is for creating frequency array and second O(n²) is for find the next greater frequency element for each element of original array.

C++ Program to find the next greater frequency element is as follows:

 /* C++ Program to find the next greater frequency element */
#include<bits/stdc++.h>
using namespace std;
void nextgreaterFreq(int arr[], int n)
{
    /* Create a frequency array and find the frequency of each element of the array */
    int freq[n];
    for(int i = 0; i < n; i++)
    {
        int count = 0;
        for(int j = 0; j < n; j++)
        {
            if(arr[i] == arr[j])
            count++;
        }
        freq[i] = count;
    }
    
    /* 
       Create a resultant array whic =h will store the 
       next greater frequency element for each element
    */
    int res[n];
    for(int i = 0; i < n; i++)
    {
        /* Initializing with '-1' if there is no next higher frequency element */
        res[i] = -1;
        /* Find the next greater frequency element */
        for(int j = i+1; j < n; j++)
        {
            if(freq[j] > freq[i])
            {
                res[i] = arr[j];
                break;
            }
        }
    }
    
    /* Print the resultant array */
    cout<<"The next greater frequency element of every element are as follows:\n";
    for(int i = 0; i < n; i++)
    cout<<res[i]<<" ";
}
int main()
{
    int arr[] = {15, 13, 12, 15, 15, 13};
    int size = sizeof(arr)/sizeof(arr[0]);
    nextgreaterFreq(arr,size);
}

OUTPUT:
The next greater frequency element of every element are as follows:
-1 15 15 -1 -1 -1

METHOD 2: Stack Based Approach

1. Create a hashmap and store the frequency of each element of the original array into the hashmap.
2. Create a resultant array of size ‘n’.
3. Create an empty stack and push zero ‘0’, the first index of the array, into the stack.
4. Scan the array elements from index ‘1’ to ‘n-1’ and do the following for each element:
5. If the frequency of the element which is pointed by the stack top is greater than frequency of the current element then push the current index ‘i’ in stack.
6. If the frequency of the element which is pointed by the stack top is less than frequency of the current element, then pop the stack elements until we find the element pointed by stack top whose frequency is greater than the current element or the stack is not empty. Then, push the index ‘i’ into the stack.
7. After completely scanning the array, pop all remaining elements from the stack and assign ‘-1’ as the result to the remaining element.
8. Print the resultant array.

The time complexity of above solution is O(nlogn), where ‘n’ is to scan the array and logn for searching into the map.

C++ Program to find the next greater frequency element is as follows:

/* C++ Program to find the next greater frequency element */
#include<bits/stdc++.h>
using namespace std;
void nextgreaterFreq(int arr[], int n)
{
    /*  Create a Hashmap and store the frequency of ecah element in it */
    map<int,int> mp;
    for(int i = 0; i < n; i++)
    {
        mp[arr[i]]++;
    }
    
    /* Create a stack and push first index '0' into it */
    stack<int> st;
    st.push(0);
    
    int res[n] = {0};
    
    for(int i = 1; i < n; i++)
    {
        /* 
        If the frequency of the element which is pointed by the stack top is greater  
        than frequency of the current element, then push the current index i into the  stack 
        */
        if (mp[arr[st.top()]] > mp[arr[i]]) 
            st.push(i); 
        else
        {
            /* If the frequency of the element which is pointed by the stack top is 
            less than frequency of the current element, then pop the stack elements until we 
            find the element pointed by stack top whose frequency is greater than the 
            current element or the stack is not empty. Then, push the index ‘i’ into the stack. */
            while (mp[arr[st.top()]] < mp[arr[i]] && !st.empty()) 
            { 
  
                res[st.top()] = arr[i]; 
                st.pop(); 
            } 
            //  Push the current element index
            st.push(i);
        }
    }
    /*
        Pop all remaining elements from the stack and assign 
        ‘-1’ as the result to the remaining element.
    */
    while (!st.empty()) 
    { 
        res[st.top()] = -1; 
        st.pop(); 
    } 
    
    cout<<"The next greater frequency elements are as follows:\n";
    for (int i = 0; i < n; i++) 
    { 
        cout << res[i] << " "; 
    }
}
int main()
{
    int arr[] = {15, 13, 12, 15, 15, 13};
    int size = sizeof(arr)/sizeof(arr[0]);
    nextgreaterFreq(arr,size);
}

OUTPUT:
The next greater frequency elements are as follows:
-1 15 15 -1 -1 -1

Related Posts:

1. Sort a Stack using Temporary Stack
2. Infix to Postfix Conversion
3. Infix to Prefix Conversion
4. Prefix to Infix Conversion
5. Prefix to Postfix Conversion
6. Postfix to Infix Conversion
7. Postfix to Prefix Conversion
8. Check whether given Parentheses String are Balanced Parentheses or Not.
9. Next Greater Element
10. Find First Non-Repeating Character of the String.
11. Find Most Frequent Element of the Array.
12. Find Minimum number of bracket reversals required to make an expression balanced.
13. Implement Queue Using Two Stacks.
14. Merge Overlapping Intervals using Stacks
15. Implement Stack Using Linked List
16. Largest Rectangular Area in Histogram
17. Length of Longest Valid Substring
18. Reverse a String using Stack
19. Implement two stacks in a single array
20. Print Bracket Number