Next element with greater frequency

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

For each element, find the next element to the right with strictly greater frequency.

Intuition

For each element, find the next element to the right with strictly greater frequency.

Algorithm

1Precompute frequencies. Use monotonic stack: pop when freq[arr[top]] < freq[arr[i]]. Record answer.

Common Pitfalls

• Two-pass: frequency count, then monotonic stack scan. O(n) total.

Next element with greater frequency.java

Java

// Approach: Precompute frequency map. Monotonic stack: push indices, pop when a more frequent element is found.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<Integer> findGreater(int[] arr) {
        ArrayList<Integer> a = new ArrayList<>(Collections.nCopies(arr.length, -1));
        Map<Integer, Integer> m = new HashMap<>();
        Stack<Integer> s = new Stack<>();

        for (int i : arr)
            m.put(i, m.getOrDefault(i, 0) + 1);

        for (int i = arr.length - 1; i >= 0; i--) {
            while (!s.isEmpty() && m.get(s.peek()) <= m.get(arr[i]))
                s.pop();

            if (!s.isEmpty())
                a.set(i, s.peek());

            s.push(arr[i]);
        }
        
        return a;
    }
}

Was this solution helpful?