Next element with greater frequency

JavaView on GFG

Time: O(n)

Space: O(n)

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?