Introduction
The Next Element With Greater Frequency problem is a variation of the famous Next Greater Element (NGE) problem.
Instead of finding the next element with a greater value, we need to find the first element on the right whose frequency of occurrence in the entire array is greater than the frequency of the current element.
This problem combines two important concepts:
Let's understand how to solve it in O(n) time.
Problem Statement
Given an array:
arr[]
For every element, find the first element on its right that has a higher frequency than the current element.
If no such element exists, return:
-1
for that position.
Example 1
Input
arr = [2, 1, 1, 3, 2, 1]
Frequency Table
1 → 3
2 → 2
3 → 1
Result
[1, -1, -1, 2, 1, -1]
Explanation
For:
arr[0] = 2
Frequency:
2
Next element having frequency greater than 2:
1
Frequency:
3
Hence answer:
1
Example 2
Input
[5,1,5,6,6]
Frequency Table
1 → 1
5 → 2
6 → 2
Output
[-1,5,-1,-1,-1]
For:
1
the next element:
5
has frequency:
2
Therefore answer:
5
Brute Force Approach
For every element:
Pseudocode
for i = 0 to n-1
for j = i+1 to n-1
if freq[arr[j]] > freq[arr[i]]
answer = arr[j]
break
Complexity
O(n²)
This is too slow for:
n = 100000
Key Observation
This problem is almost identical to:
Next Greater Element
The only difference:
Instead of comparing values:
arr[j] > arr[i]
we compare frequencies:
freq[arr[j]] > freq[arr[i]]
Therefore, we can use a Monotonic Stack.
Frequency Map
First, count frequencies.
Example:
[2,1,1,3,2,1]
HashMap:
1 → 3
2 → 2
3 → 1
Now every frequency lookup becomes:
O(1)
Monotonic Stack Idea
Process elements from:
Right → Left
The stack stores candidate elements that may become answers.
For every element:
Remove all elements whose frequency is:
<= current frequency
because they cannot be the next greater frequency element.
The first remaining element on the stack becomes the answer.
Why Does This Work?
Consider:
arr = [2,1,1,3,2,1]
Frequencies:
2 → 2
1 → 3
3 → 1
Processing from right:
1
2
3
1
1
2
Whenever an element with lower or equal frequency appears, it gets removed because it cannot help future elements.
Thus every element is:
giving O(n) complexity.
Algorithm
Step 1
Build the frequency map.
HashMap<Integer,Integer> freq
Step 2
Initialize:
Stack<Integer> st
Store array elements.
Step 3
Traverse from right to left.
Step 4
While:
freq[stackTop] <= freq[current]
pop the stack.
Step 5
If the stack becomes empty:
answer = -1
Otherwise:
answer = stackTop
Step 6
Push the current element into the stack.
Dry Run
Input
[2,1,1,3,2,1]
Frequency:
1 → 3
2 → 2
3 → 1
Index 5
1
Stack empty:
ans = -1
Push:
1
Index 4
2
Frequency:
2
Top:
1
Frequency:
3
Greater frequency exists.
Answer:
1
Push:
2
Index 3
3
Frequency:
1
Top:
2
Frequency:
2
Answer:
2
Continue similarly:
Result:
[1,-1,-1,2,1,-1]
Java Solution
class Solution {
public ArrayList<Integer> nextFreqGreater(int[] arr) {
int n = arr.length;
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
ArrayList<Integer> ans =
new ArrayList<>(Collections.nCopies(n, -1));
Stack<Integer> st = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() &&
freq.get(st.peek()) <= freq.get(arr[i])) {
st.pop();
}
if (!st.isEmpty()) {
ans.set(i, st.peek());
}
st.push(arr[i]);
}
return ans;
}
}
Alternative Using Array Frequency
Since:
arr[i] ≤ 100000
we can use an array instead of HashMap.
int[] freq = new int[100001];
This may be slightly faster due to O(1) indexing.
Complexity Analysis
Let:
n = array size
Frequency Counting
O(n)
Stack Processing
Each element is:
Total:
O(n)
Overall Time Complexity
O(n)
Space Complexity
Frequency map:
O(n)
Stack:
O(n)
Total:
O(n)
Why the Monotonic Stack Works
The stack maintains elements whose frequencies are strictly greater than the frequencies of elements below them.
Whenever an element with equal or greater frequency appears:
freq(top) <= freq(current)
the top can never serve as an answer for any future element and is removed.
This guarantees:
Correct answers
Linear-time processing
Edge Cases
Single Element
[5]
Output:
[-1]
All Same Elements
[1,1,1]
Output:
[-1,-1,-1]
No element has a higher frequency.
Strictly Increasing Values
[1,2,3,4]
All frequencies:
1
Output:
[-1,-1,-1,-1]
Conclusion
The Next Element With Greater Frequency problem is a clever variation of Next Greater Element.
The key insight is:
Compare frequencies instead of values.
By combining:
we obtain an optimal solution:
Time Complexity : O(n)
Space Complexity: O(n)
This approach efficiently handles arrays of size up to 100,000 and is a common interview problem involving hashing and stacks.