# Next Greater Frequency Element (Space Efficient Approach)

Hello Everyone,

Space Efficient Approach: using a hash map instead of a list as mentioned in the above approach.

Steps:

1. Create a class pair to store pair<int, int> with pair<element, frequency>.
2. Create a hasp map with pair as generics to store keys as the element and values as the frequency of every element.
3. Iterate the array and save the element and its frequency in the hashmap.
4. Create a res array that stores the resultant array.
5. Initially make res[n-1] = -1 and push the element in the end along with its frequency into the stack.
6. Iterate through the array in reverse order.
7. 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.
8. Continue till the loop fails.
9. 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.
10. 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.
11. Push the current element along with its frequency.
• Java

`// Java program of Next Greater Frequency Element`

`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;`

` ` `}`

` ` `}`

` `

` ` `/*NFG function to find the next greater frequency`

` ` `element for each element and for placing it in the`

` ` `resultant array */`

` ` `void` `NGF(` `int` `[] arr,` `int` `[] res) {`

` ` `int` `n = arr.length;`

` `

` ` `//Initially store the frequencies of all elements`

` ` `//in a hashmap`

` ` `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` `);`

` ` `}`

` `

` ` `//Get the frequency of the last element`

` ` `int` `curr_freq = mymap.get(arr[n-` `1` `]);`

` ` `//push it to the stack`

` ` `mystack.push(` `new` `Pair(arr[n-` `1` `],curr_freq));`

` ` `//place -1 as next greater freq for the last`

` ` `//element as it does not have next greater.`

` ` `res[n-` `1` `] = -` `1` `;`

` `

` ` `//iterate through array in reverse order`

` ` `for` `(` `int` `i = n-` `2` `;i>=` `0` `;i--) {`

` ` `curr_freq = mymap.get(arr[i]);`

` `

` ` `/* 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*/`

` ` `while` `(!mystack.isEmpty() && curr_freq >= mystack.peek().freq)`

` ` `mystack.pop();`

` `

` ` `//If the stack is empty, place -1. If it is not empty`

` ` `//then we will have next higher freq element at the top of the stack.`

` ` `res[i] = (mystack.isEmpty()) ? -` `1` `: mystack.peek().data;`

` `

` ` `//push the element at current position`

` ` `mystack.push(` `new` `Pair(arr[i],mymap.get(arr[i])));`

` ` `}`

` ` `}`

` `

` ` `//Driver function`

` ` `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));`

` ` `}`

`}`

Output

[2, 2, 2, -1, -1, -1, -1, 3, -1, -1]

Time Complexity: O(n).