Next Element With Greater Frequency – Java O(n) Stack Solution

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:

Hashing (to count frequencies)
Monotonic Stack (to efficiently find the next qualifying element)

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:

Next element having frequency greater than 2:

Frequency:

Hence answer:

Example 2

Input

[5,1,5,6,6]

Frequency Table

1 → 1
5 → 2
6 → 2

Output

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

For:

the next element:

has frequency:

Therefore answer:

Brute Force Approach

For every element:

Traverse all elements on the right.
Check frequencies.
Find the first element with greater frequency.

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:

Whenever an element with lower or equal frequency appears, it gets removed because it cannot help future elements.

Thus every element is:

Pushed once
Popped once

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

Stack empty:

ans = -1

Push:

Index 4

Frequency:

Top:

Frequency:

Greater frequency exists.

Answer:

Push:

Index 3

Frequency:

Top:

Frequency:

Answer:

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:

Pushed once
Popped once

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:

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:

A frequency map
A monotonic decreasing stack (based on frequency)

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.