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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Frequency Stack

Number: 931

Difficulty: Hard

Paid? No

Companies: Amazon, Uber, Microsoft, Apple, PayPal, TikTok, Salesforce

Problem Description

Design a stack-like data structure that supports push and pop operations. The pop operation removes and returns the most frequent element in the stack. In case of a tie (i.e. multiple elements have the same frequency), the element closest to the top of the stack is removed and returned.

Key Insights

  • Use a hash map to count the frequency of each element.
  • Maintain another hash map that maps frequencies to stacks (lists) of elements.
  • Track the current maximum frequency to enable O(1) retrieval of the most frequent element.
  • When pushing an element, update its frequency and add it to the corresponding frequency stack.
  • When popping an element, remove it from the stack corresponding to the maximum frequency and update the frequency count; if that stack becomes empty, decrease the current maximum frequency.

Space and Time Complexity

Time Complexity: O(1) per push and pop. Space Complexity: O(n), where n is the number of elements pushed onto the stack.

Solution

The solution involves using two main data structures:

  1. A hash map (freq) to store the frequency count for each value.
  2. A hash map (group) that maps a frequency to a stack (list) of values that have that frequency.

During a push:

  • Increment the frequency count of the value.
  • Push the value onto the stack corresponding to its updated frequency.
  • Update the maximum frequency if necessary.

During a pop:

  • Pop the top element from the stack corresponding to the current maximum frequency.
  • Decrement its frequency count in the freq map.
  • If the frequency stack becomes empty after popping, decrement the current maximum frequency. This design enables the retrieval of the most frequent element in constant time while dealing with frequency ties by returning the element closest to the top.

Code Solutions

# Python implementation of FreqStack

class FreqStack:
    def __init__(self):
        # Dictionary mapping value to its frequency
        self.freq = {}
        # Dictionary mapping frequency to a list (stack) of values
        self.group = {}
        # Variable tracking the current maximum frequency in the stack
        self.maxfreq = 0

    def push(self, val: int) -> None:
        # Update frequency count for the value
        f = self.freq.get(val, 0) + 1
        self.freq[val] = f
        # Update the maximum frequency if necessary
        if f > self.maxfreq:
            self.maxfreq = f
        # Append the value to the appropriate frequency group
        if f not in self.group:
            self.group[f] = []
        self.group[f].append(val)

    def pop(self) -> int:
        # Remove the value from the stack of the current maximum frequency
        val = self.group[self.maxfreq].pop()
        # Decrement the frequency count for the value
        self.freq[val] -= 1
        # If no more elements have the current max frequency, decrease maxfreq
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return val
← Back to All Questions