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:

Code
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:

Code
-1

for that position.

Example 1

Input

Code
arr = [2, 1, 1, 3, 2, 1]

Frequency Table

Code
1 → 3
2 → 2
3 → 1

Result

Code
[1, -1, -1, 2, 1, -1]

Explanation

For:

Code
arr[0] = 2

Frequency:

Code
2

Next element having frequency greater than 2:

Code
1

Frequency:

Code
3

Hence answer:

Code
1

Example 2

Input

Code
[5,1,5,6,6]

Frequency Table

Code
1 → 1
5 → 2
6 → 2

Output

Code
[-1,5,-1,-1,-1]

For:

Code
1

the next element:

Code
5

has frequency:

Code
2

Therefore answer:

Code
5

Brute Force Approach

For every element:

Pseudocode

Code
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

Code
O(n²)

This is too slow for:

Code
n = 100000

Key Observation

This problem is almost identical to:

Code
Next Greater Element

The only difference:

Instead of comparing values:

Code
arr[j] > arr[i]

we compare frequencies:

Code
freq[arr[j]] > freq[arr[i]]

Therefore, we can use a Monotonic Stack.

Frequency Map

First, count frequencies.

Example:

Code
[2,1,1,3,2,1]

HashMap:

Code
1 → 3
2 → 2
3 → 1

Now every frequency lookup becomes:

Code
O(1)

Monotonic Stack Idea

Process elements from:

Code
Right → Left

The stack stores candidate elements that may become answers.

For every element:

Remove all elements whose frequency is:

Code
<= 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:

Code
arr = [2,1,1,3,2,1]

Frequencies:

Code
2 → 2
1 → 3
3 → 1

Processing from right:

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

Java
HashMap<Integer,Integer> freq

Step 2

Initialize:

Java
Stack<Integer> st

Store array elements.

Step 3

Traverse from right to left.

Step 4

While:

Code
freq[stackTop] <= freq[current]

pop the stack.

Step 5

If the stack becomes empty:

Code
answer = -1

Otherwise:

Code
answer = stackTop

Step 6

Push the current element into the stack.

Dry Run

Input

Code
[2,1,1,3,2,1]

Frequency:

Code
1 → 3
2 → 2
3 → 1

Index 5

Code
1

Stack empty:

Code
ans = -1

Push:

Code
1

Index 4

Code
2

Frequency:

Code
2

Top:

Code
1

Frequency:

Code
3

Greater frequency exists.

Answer:

Code
1

Push:

Code
2

Index 3

Code
3

Frequency:

Code
1

Top:

Code
2

Frequency:

Code
2

Answer:

Code
2

Continue similarly:

Result:

Code
[1,-1,-1,2,1,-1]

Java Solution

Java
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:

Code
arr[i] ≤ 100000

we can use an array instead of HashMap.

Java
int[] freq = new int[100001];

This may be slightly faster due to O(1) indexing.

Complexity Analysis

Let:

Code
n = array size

Frequency Counting

Code
O(n)

Stack Processing

Each element is:

Total:

Code
O(n)

Overall Time Complexity

Code
O(n)

Space Complexity

Frequency map:

Code
O(n)

Stack:

Code
O(n)

Total:

Code
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:

Code
freq(top) <= freq(current)

the top can never serve as an answer for any future element and is removed.

This guarantees:

Edge Cases

Single Element

Code
[5]

Output:

Code
[-1]

All Same Elements

Code
[1,1,1]

Output:

Code
[-1,-1,-1]

No element has a higher frequency.

Strictly Increasing Values

Code
[1,2,3,4]

All frequencies:

Code
1

Output:

Code
[-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:

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