Next Greater Frequency Element

Medium
1419.

Next Greater Frequency Element

Next Greater Frequency Element is a medium coding problem on arrays, hash table and stack, asked in Amazon, Flipkart and Paytm interviews.

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^5
  • 1 <= arr[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var nextGreaterFrequency = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= arr[i] <= 10^5

Hints for Next Greater Frequency Element

  1. Hint 1

    First count every value's frequency; after that, the problem is 'next greater element' with frequencies in place of values.

  2. Hint 2

    Walk from right to left. Which elements to your right can never be the answer for anything further left?

  3. 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

  1. Count the frequency of every value.
  2. Scan i from n - 1 down to 0 with a stack of values.
  3. Pop while the top's frequency is <= the frequency of arr[i].
  4. The answer for i is the top's value, or -1 if the stack is empty; then push arr[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 res

Java

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