# Next Greater Frequency Element

Given an array, for each element find the value of nearest element to the right which is having frequency greater than as that of 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 index is be used to store frequency of each element. Create a list suppose to store 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 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 stack data structure to store position of elements in the array.

1) Create a list to to use values as index to store frequency of each element.
2) Push the position of first element to stack.
3) Pick rest of the position of elements one by one and follow following steps in loop.
…….a) Mark the position of current element as ‘i’ .
……. b) 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
……. c) 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:
…….i) continue popping the stack
…….ii) if the condition in step c fails then push the current position i to the stack
4) 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.

Time complexity is O(n).

Below is the Python 3 implementation of the above problem.

`'''NFG function to find the next greater frequency`
`   ``element for each element in the array'''`
`def` `NFG(a, n):`
`    `
`    ``if` `(n <``=` `0``):`
`        ``print``(``"List empty"``)`
`        ``return` `[]`
`    ``# stack data structure to store the position `
`    ``# of array element `
`    ``stack ``=` `[``0``]``*``n`
`    ``# freq is a dictionary which maintains the `
`    ``# frequency of each element`
`    ``freq ``=` `{}`
`    ``for` `i ``in` `a:`
`        ``freq[a[i]] ``=` `0`
`    ``for` `i ``in` `a:`
`        ``freq[a[i]] ``+``=` `1`
`    ``# res to store the value of next greater `
`    ``# frequency element for each element`
`    ``res ``=` `[``0``]``*``n`
`    ``# initialize top of stack to -1`
`    ``top ``=` `-``1`
`    ``# push the first position of array in the stack`
`    ``top ``+``=` `1`
`    ``stack[top] ``=` `0`
`    `
`    ``# now iterate for the rest of elements`
`    ``for` `i ``in` `range``(``1``, n):`
`        ``''' If the frequency of the element which is `
`            ``pointed by the top of stack is greater `
`            ``than frequency of the current element`
`            ``then push the current position i in stack'''`
`        ``if` `(freq[a[stack[top]]] > freq[a[i]]):`
`            ``top ``+``=` `1`
`            ``stack[top] ``=` `i`
`        ``else``: `
`            ``''' If the frequency of the element which `
`            ``is pointed by the top of stack is less `
`            ``than frequency of the current element, then `
`            ``pop the stack and continuing popping until `
`            ``the above condition is true while the stack`
`            ``is not empty'''`
`            `
`            ``while` `(top>``-``1` `and` `freq[a[stack[top]]] < freq[a[i]]):`
`                ``res[stack[top]] ``=` `a[i]`
`                ``top ``-``=` `1`
`            ``# now push the current element`
`            ``top``+``=``1`
`            ``stack[top] ``=` `i`
`            `
`    ``'''After iterating over the loop, the remaining`
`    ``position of elements in stack do not have the `
`    ``next greater element, so print -1 for them'''`
`    ``while` `(top > ``-``1``):`
`        ``res[stack[top]] ``=` `-``1`
`        ``top ``-``=` `1`
`    ``# return the res list containing next `
`    ``# greater frequency element`
`    ``return` `res`
`# Driver program to test the function`
`print``(NFG([``1``,``1``,``2``,``3``,``4``,``2``,``1``],``7``))`

Output:

```[-1, -1, 1, 2, 2, 1, -1]

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at