Maximum Frequency Stack

Updated on 10 June, 2025
Maximum Frequency Stack header image

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

  • Java
java
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;
    }
}

The provided Java solution implements a data structure known as a "Maximum Frequency Stack" which allows for efficient querying, insertion, and deletion based on the frequency of elements. The code utilizes two primary data structures:

  • A Map<Integer, Integer> named frequency to track the frequency of each element pushed into the stack. The key represents the element, and the value represents the frequency of that element in the stack.
  • A Map<Integer, Stack<Integer>> named level, where keys are frequencies and values are stacks that store elements with the corresponding frequency.

Explanation of the Methods:

  1. Constructor FrequencyStack(): Initializes the frequency and level maps and sets highestFrequency to 0. This variable keeps track of the maximum frequency of any element in the stack at any given time.

  2. Method push(int x):

    • Increments the frequency of the element x in the frequency map.
    • Updates highestFrequency if the frequency of x surpasses the current highestFrequency.
    • Adds element x to the stack corresponding to its updated frequency in the level map.
  3. Method pop():

    • Retrieves and removes the top element of the stack associated with highestFrequency.
    • Decrements the frequency of the popped element in the frequency map.
    • If the stack for the current highestFrequency becomes empty after the pop, decreases highestFrequency by 1.
    • Returns the popped element.

This design ensures that push() and pop() operations are efficient, optimized for the scenario where quick access to the most frequently accessed elements is needed. The use of maps for frequency and grouping elements by their frequencies allows for fast lookups and adjustments, accommodating the stack's behavior which revolves around element frequency. The code is robust and handles edge cases such as popping when multiple elements have the same highest frequency.

Comments

No comments yet.