We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Frequency Stack

Difficulty: Hard

Problem Description

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

  • FreqStack() constructs an empty frequency stack.
  • void push(int val) pushes an integer val onto the top of the stack.
  • int pop() removes and returns the most frequent element in the stack.
    • If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

Key Insights

  • Track the frequency of each element using a hash table.
  • Maintain a stack for each frequency to easily pop the most frequent element.
  • Ensure efficient push and pop operations to meet the problem's constraints.

Space and Time Complexity

Time Complexity: O(1) for both push and pop operations on average.
Space Complexity: O(n) where n is the number of distinct elements pushed onto the stack.

Solution

To solve the problem, we utilize two main data structures:

  1. A hash table (dictionary) to record the frequency of each element.
  2. A list of stacks (array of stacks) where the index corresponds to the frequency of the elements. This allows us to directly access the stack of the most frequent elements.

When pushing an element, we increment its frequency in the hash table and push it onto the corresponding stack. When popping, we check the highest index in our list of stacks (which represents the highest frequency), pop from that stack, decrement the frequency of the element, and update the hash table accordingly.

Code Solutions

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.stacks = []
        self.max_freq = 0

    def push(self, val: int) -> None:
        if val in self.freq:
            self.freq[val] += 1
        else:
            self.freq[val] = 1

        freq = self.freq[val]
        if freq > self.max_freq:
            self.max_freq = freq
            self.stacks.append([])

        self.stacks[freq - 1].append(val)

    def pop(self) -> int:
        if self.max_freq == 0:
            return None

        val = self.stacks[self.max_freq - 1].pop()
        self.freq[val] -= 1

        if not self.stacks[self.max_freq - 1]:
            self.max_freq -= 1

        return val
← Back to All Questions