Last Updated on September 13, 2022 by Gokul Kannan
Problem statement
Given an array, consisting of n elements, find the next greater frequency element of each element. The next greater frequency element of any element is the first element to its right having a greater frequency than its own frequency.
Input: Integer array of size of n.
Output: Integer array of size n.
Test cases:
Input:
[1, 4, 2, 4, 2, 3, 2]
Output:
[4, 2, -1, 2, -1, 2, -1]
Explanation:
Frequency of 1 -> 1
Frequency of 2 -> 3
Frequency of 4 -> 2
Frequency of 3 -> 1
- Output[0] = 4 because next to 1 there is 4 and frequency of 4 is greater than 1.
- Output[1] = 2 because next to 4 there is 2 and frequency of 2 is greater than 4.
- Output[2] = -1 because 2 does not have any lament to its right having a frequency greater than its own.
- Output[3] = 2 because next to 4 there is 2 and frequency of 2 is greater than 4.
- Output[4] = -1 because 2 does not have any lament to its right having a frequency greater than its own.
- Output[5] = 2 because next to 3 there is 2 and frequency of 2 is greater than 3.
- Output[6] = -1 because 2 does not have any element to its right.
Naive Approach – Brute Force
The idea is to use a hashing. The hashmap will be used to store key-value pairs, where key will be any element of the array and the value be the frequency of that element.
After creating the required hashmap, we will iterate each element of the given array and for each element we will check all the elements to its right.
If after checking all the elements to the right we still do not find the next greater frequency element, then the answer for that element will be -1, otherwise the answer for that element will be the first element we find with a greater frequency than it.
Algorithm
1. Initialize an empty stack and an array.
2. Calculate frequency of each element and store it in the map.
3. For each i in 0 to n:
a. For each j in i + 1 to n
i. If frequency of arr[j] > frequency of arr[i],
then ans[i] = arr[j]
b. If we does not found the next greater frequency
element, then ans[i] = -1
4. Return ans array.Code Implementation:
import java.util.HashMap;
class Prepbytes {
// This function will find the next greater frequency element for each
// element
public static int[] nextGFE(int arr[], int n)
{
HashMap<Integer, Integer> map = new HashMap<>();
int ans[] = new int[n];
for(int e : arr){
map.put(e, map.getOrDefault(e, 0)+1);
}
for(int i = 0; i < n; i++){
boolean found = false;
for(int j = i+ 1; j< n;j++){
if(map.get(arr[j])>map.get(arr[i])){
ans[i] = arr[j];
found = true;
break;
}
}
if(!found){
ans[i] = -1;
}
}
return ans;
}
public static void main(String[] args) {
int arr[] = new int[]{1, 4, 2, 4, 2, 3, 2};
int ans[] = nextGFE(arr, arr.length);
for(int e : ans){
System.out.print(e+" ");
}
}
}
Output:
4 2 -1 2 -1 2 -1
Time complexity: O(n^2). It takes O(n) to find the next greater frequency element of one element, and we have to find n elements. Hence, the time complexity will be O(n^2)
Space Complexity: O(n). The space required is only for the input and output array. The auxiliary space complexity is O(1).
Efficient Approach – Using Stack
The idea is to use hashing and stack. The hashmap will be used to store key-value pairs, where key will be any element of the array and the value be the frequency of that element.
The stack will be used to store the element in a monotonically increasing order according to their frequencies.
We will iterate every element in the given array. For each element, while the stack is not empty and the frequency of the current element is greater than the frequency of the top of the stack, we will keep removing the top of the stack. After the while loop terminates, there could be two possible cases:
Case 1: The stack is empty. If the stack is empty it means that there were no elements having a frequency greater than the current element. Hence, we will set ans[i] as -1.
Case 2: We found an element having a frequency greater than the current element. Then we will set ans[i] as the top of the stack.
Algorithm
1. Initialize an empty stack, map and an array.
2. Calculate frequency of each element and store it in the map.
3. Iterate i from 0 to n.
a. While stack is not empty and the frequency of the current element
is greater than the frequency of the top of the stack
i. Remove the top the stack
b. If the stack is empty, then it mean there is
no next greater frequency element for this element
i. ans[i] = -1.
c. Otherwise, ans[i] = top of the stack
d. Push the current element to the stack
4. Return ans array.Code Implementation:
import java.util.Stack;
import java.util.HashMap;
class Prepbytes {
// This function will find the next greater frequency element for each
// element
public static int[] nextGFE(int arr[], int n)
{
// This map will store the element of the array as key
// and there frequency as value
HashMap<Integer, Integer> map = new HashMap<>();
Stack<Integer> st = new Stack<>();
int ans[] = new int[n];
// Calculate frequency of each element
for(int e : arr){
map.put(e, map.getOrDefault(e, 0)+1);
}
// Iterate over the given array
for(int i = n - 1; i>= 0; i--){
// While stack is not empty and the frequency of the current
// element is greater than the frequency of the top of the
// stack, keeping removing the top of the stack
while(!st.isEmpty() && map.get(arr[i]) >= map.get(st.peek())){
st.pop();
}
// If the stack is empty, then it mean there is no next greater
// frequency element for this element
if(st.isEmpty()){
ans[i] = -1;
}
// Otherwise, the top of the stack is the next greater
// frequency element for this element
else {
ans[i] = st.peek();
}
// Push the current element to the stack
st.push(arr[i]);
}
return ans;
}
public static void main(String[] args) {
int arr[] = new int[]{1, 4, 2, 4, 2, 3, 2};
int ans[] = nextGFE(arr, arr.length);
for(int e : ans){
System.out.print(e+" ");
}
}
}
Output:
4 2 -1 2 -1 2 -1
Time complexity: O(n). We can observe that every element is pushed and removed from the stack only once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don’t consider constant terms during asymptotic analysis of time complexity.
Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is O(n) as we are using a stack and a map. At any point of time the stack can contain at most n elements and the map can contain 2n elements.
This article tried to discuss the most efficient way to find the next greater frequency element. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.