Next Greater Frequency Element — Problem & Solution
Next Greater Frequency Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Next Greater Frequency Element is a medium coding problem on arrays, hash table and stack, asked in Amazon, Flipkart and Paytm interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Stack, Monotonic Stack
- Asked at: Amazon, Flipkart, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The frequency of a value is how many times it occurs in the whole array arr.
For every index i, find the nearest index j > i whose value occurs strictly more often in arr than arr[i] does, and report arr[j]. If no such index exists, report -1.
Return the array of reports.
Example 1
Input: arr = [5,1,5,6,6,6]
Output: [6,5,6,-1,-1,-1]
Explanation: Frequencies: 5 → 2, 1 → 1, 6 → 3. For the 1 at index 1, the next value seen more often is the 5 at index 2.
Example 2
Input: arr = [4,4,4]
Output: [-1,-1,-1]
Example 3
Input: arr = [7,3,3,9,7,7]
Output: [-1,7,7,7,-1,-1]
Explanation: 7 is the most frequent value (3 times), so nothing beats it.
Constraints
1 <= arr.length <= 10^51 <= arr[i] <= 10^5
Hints for Next Greater Frequency Element
Hint 1
First count every value's frequency; after that, the problem is 'next greater element' with frequencies in place of values.
Hint 2
Walk from right to left. Which elements to your right can never be the answer for anything further left?
Hint 3
Keep a stack of values whose frequencies strictly increase from top to bottom: pop every value whose frequency is
<=the current one, report the top (or -1), then push the current value.
How to solve Next Greater Frequency Element
With frequencies precomputed, each position asks for the next element of strictly higher frequency — the next-greater-element pattern, solved with a monotonic stack scanned from the right.
Approach
- Count the frequency of every value.
- Scan
ifromn - 1down to 0 with a stack of values. - Pop while the top's frequency is
<=the frequency ofarr[i]. - The answer for
iis the top's value, or -1 if the stack is empty; then pusharr[i].
Why it works
A popped value at position j > i has frequency at most freq(arr[i]). Any position further left that would accept it (its own frequency below freq(arr[j])) would also accept arr[i], which is nearer — so j is never needed again. The stack therefore holds exactly the possible answers, with the nearest one on top.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Compare frequencies, not values — but report the value.
- Strictly greater: an equal frequency does not count, so pop on
<=. - Frequencies are global, counted over the whole array, not over the suffix.
Reference solution
Python
from typing import List
from collections import Counter
def nextGreaterFrequency(arr: List[int]) -> List[int]:
freq = Counter(arr)
n = len(arr)
res = [-1] * n
st = []
for i in range(n - 1, -1, -1):
f = freq[arr[i]]
while st and freq[st[-1]] <= f:
st.pop()
if st:
res[i] = st[-1]
st.append(arr[i])
return resJava
public static int[] nextGreaterFrequency(int[] arr) {
int n = arr.length;
Map<Integer, Integer> freq = new HashMap<>();
for (int x : arr) freq.merge(x, 1, Integer::sum);
int[] res = new int[n];
int[] st = new int[n];
int top = 0;
for (int i = n - 1; i >= 0; i--) {
int f = freq.get(arr[i]);
while (top > 0 && freq.get(st[top - 1]) <= f) top--;
res[i] = top > 0 ? st[top - 1] : -1;
st[top++] = arr[i];
}
return res;
}C++
vector<int> nextGreaterFrequency(vector<int>& arr) {
int n = arr.size();
unordered_map<int, int> freq;
for (int x : arr) freq[x]++;
vector<int> res(n, -1), st;
for (int i = n - 1; i >= 0; i--) {
int f = freq[arr[i]];
while (!st.empty() && freq[st.back()] <= f) st.pop_back();
if (!st.empty()) res[i] = st.back();
st.push_back(arr[i]);
}
return res;
}JavaScript
var nextGreaterFrequency = function(arr) {
var n = arr.length;
var freq = new Map();
for (var i = 0; i < n; i++) freq.set(arr[i], (freq.get(arr[i]) || 0) + 1);
var res = new Array(n).fill(-1);
var st = [];
for (var j = n - 1; j >= 0; j--) {
var f = freq.get(arr[j]);
while (st.length > 0 && freq.get(st[st.length - 1]) <= f) st.pop();
if (st.length > 0) res[j] = st[st.length - 1];
st.push(arr[j]);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets