Maximum Frequency Stack

Problem Statement

The task is to design a specialized stack data structure, named FreqStack, which extends the basic functionalities of a typical stack. FreqStack supports standard push operations but has a unique feature for its pop operation. Unlike a regular stack that follows the Last-In-First-Out (LIFO) principle, the FreqStack's pop operation removes the most frequently added element. If two or more elements have the same frequency, then the element closest to the top of the stack is removed.

This requires implementing both:

• push(int val) to add an element.
• pop() to remove the element based on the stipulated conditions from the stack.

Examples

Example 1

Input:

["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]

Input Arguments:

[[], [5], [7], [5], [7], [4], [5], [], [], [], []]

Output:

[null, null, null, null, null, null, null, 5, 7, 5, 4]

Explanation:

FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4]
freqStack.pop();   // return 7, as 5 and 7 are the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4]
freqStack.pop();   // return 4, as 4, 5, and 7 are the most frequent, but 4 is closest to the top. The stack becomes [5,7]

Constraints

• 0 <= val <= 10^9
• At most 2 * 10^4 calls will be made to push and pop.
• It is guaranteed that there will be at least one element in the stack before calling pop.

Approach and Intuition

In order to effectively manage the unique characteristics of FreqStack, particularly the pop() operation, here’s a structured approach:

1. Track Element Frequencies:

   • Maintain a dictionary (freq) that stores the frequency of each element pushed onto the stack.

2. Maintain a Stack of Stacks Based on Frequencies:

   • Use an additional dictionary (group) where each key corresponds to a frequency, and each value is a stack (or list) containing the elements that appear with that frequency.
   • This structure allows you to quickly retrieve the element with the highest frequency and preserve the order of insertion.

3. Implement push(int val):

   • Increase the frequency of val in the freq dictionary.
   • Push val onto the corresponding stack in group[freq[val]].
   • Keep track of the current maximum frequency (maxfreq) seen so far.

4. Implement pop():

   • Pop the element from the stack corresponding to maxfreq.
   • Decrease its frequency in freq.
   • If the stack for maxfreq becomes empty after popping, decrement maxfreq since there are no more elements at that frequency.

5. Efficiency:

   • Both push and pop operate in O(1) time on average due to the efficient use of dictionaries and stacks.
   • The design ensures that we always know the current most frequent element and can retrieve it in constant time.

Solutions

class FrequencyStack {
    Map<Integer, Integer> frequency;
    Map<Integer, Stack<Integer>> level;
    int highestFrequency;
    
    public FrequencyStack() {
        frequency = new HashMap<>();
        level = new HashMap<>();
        highestFrequency = 0;
    }
    
    public void push(int x) {
        int count = frequency.getOrDefault(x, 0) + 1;
        frequency.put(x, count);
        if (count > highestFrequency)
            highestFrequency = count;
    
        level.computeIfAbsent(count, z -> new Stack<>()).push(x);
    }
    
    public int pop() {
        int x = level.get(highestFrequency).pop();
        frequency.put(x, frequency.get(x) - 1);
        if (level.get(highestFrequency).isEmpty())
            highestFrequency--;
        return x;
    }
}