Problem Description

You need to design a special stack data structure called FreqStack that supports two operations:

1. Push: Add an element to the stack
2. Pop: Remove and return the element that appears most frequently in the stack

The key challenge is that when you pop, you don't just remove any occurrence of the most frequent element - you need to follow specific rules:

• Find the element(s) with the highest frequency count
• If multiple elements share the same highest frequency, remove the one that was pushed most recently (closest to the top)

For example, if you push the sequence [5, 7, 5, 7, 4, 5]:

• Element 5 appears 3 times (highest frequency)
• Elements 7 appears 2 times
• Element 4 appears 1 time

When you call pop(), it should return 5 because it has the highest frequency. The specific 5 removed would be the last one pushed.

If after that pop you have [5, 7, 5, 7, 4] and call pop() again:

• Both 5 and 7 now appear 2 times (tied for highest frequency)
• Since 7 was pushed more recently than the remaining 5, it returns 7

The implementation uses:

• A hash table cnt to track the frequency of each element
• A max heap q that stores tuples of (-frequency, -timestamp, value) to efficiently find the most frequent and most recent element
• A timestamp counter ts to track the order of insertions

The negative values in the heap ensure that higher frequencies and more recent timestamps have priority when popping elements.

Intuition

When thinking about this problem, we need to handle two key requirements: tracking frequency and maintaining recency when frequencies are tied.

The first thought might be to use a simple frequency counter, but that alone won't help us efficiently find the element with maximum frequency. We'd have to scan through all elements every time we pop, which would be inefficient.

This naturally leads us to consider a heap (priority queue) since it can give us the maximum element in O(log n) time. But what should we store in the heap?

We need to prioritize by frequency first, so that should be our primary sorting criterion. However, when frequencies are equal, we need the most recently pushed element. This means we need to track when each element was pushed - hence the need for timestamps.

The clever insight is to combine both frequency and timestamp into a single tuple for the heap. By using (-frequency, -timestamp, value), we create a max heap where:

• Higher frequencies come first (more negative means higher priority in a min heap)
• Among equal frequencies, larger timestamps come first (more recent pushes)

Why don't we remove elements from the heap when their frequency decreases? This would require searching through the heap, which is expensive. Instead, we use a "lazy deletion" approach - we keep all entries in the heap and only check if they're valid when we pop them. The frequency counter cnt tells us the current actual frequency of each element.

When we pop, we get the top element from the heap. Since we decrement its frequency in cnt, any outdated entries for this element in the heap (with higher frequencies) will naturally be ignored in future operations because we always use the most recent frequency when pushing new entries.

This approach elegantly handles both requirements with O(log n) complexity for both push and pop operations.

Learn more about Stack patterns.

Solution Approach

The solution uses a hash table combined with a priority queue (max heap) to efficiently track and retrieve the most frequent elements.

Data Structures Used:

1. Hash Table cnt: A defaultdict(int) that maintains the current frequency count for each element in the stack.

2. Priority Queue q: A max heap implemented using Python's heapq (which is a min heap by default, so we use negative values). Each entry is a tuple (-frequency, -timestamp, value).

3. Timestamp Counter ts: An integer that increments with each push operation to track the order of insertions.

Implementation Details:

Initialization (__init__):

• Initialize cnt as an empty frequency counter
• Initialize q as an empty list (will be used as a heap)
• Set ts = 0 as the starting timestamp

Push Operation (push):

1. Increment the timestamp: self.ts += 1
2. Update the frequency count: self.cnt[val] += 1
3. Add a new entry to the heap: heappush(self.q, (-self.cnt[val], -self.ts, val))
   • The negative frequency ensures higher frequencies have priority
   • The negative timestamp ensures more recent elements have priority when frequencies are equal
   • The actual value is stored as the third element

Pop Operation (pop):

1. Extract the top element from the heap: val = heappop(self.q)[2]
   • This gives us the element with the highest frequency
   • If frequencies are tied, it gives us the most recently pushed one
2. Decrement the frequency count: self.cnt[val] -= 1
3. Return the popped value: return val

Key Insights:

• No Heap Cleanup: The implementation doesn't remove outdated entries from the heap. When an element is popped, its frequency decreases, but old entries with higher frequencies remain in the heap. This is acceptable because:

  • We always push new entries with current frequencies
  • The heap will naturally prioritize the most recent, accurate entries
  • This avoids the costly operation of searching and removing from the heap

• Time Complexity:

  • Push: O(log n) where n is the number of entries in the heap
  • Pop: O(log n) for the heap operation

• Space Complexity: O(n) where n is the total number of push operations, as we store all entries in the heap without cleanup.

Example Walkthrough

Let's walk through a concrete example with the sequence of operations:

• push(4), push(5), push(4), push(6), push(5), push(4), pop(), pop()

Initial State:

• cnt = {} (empty frequency counter)
• q = [] (empty heap)
• ts = 0 (timestamp counter)

Step 1: push(4)

• Increment timestamp: ts = 1
• Update frequency: cnt[4] = 1
• Add to heap: heappush(q, (-1, -1, 4))
• State: cnt = {4: 1}, q = [(-1, -1, 4)]

Step 2: push(5)

• Increment timestamp: ts = 2
• Update frequency: cnt[5] = 1
• Add to heap: heappush(q, (-1, -2, 5))
• State: cnt = {4: 1, 5: 1}, q = [(-1, -2, 5), (-1, -1, 4)]
  • Note: 5 has higher priority due to more recent timestamp

Step 3: push(4)

• Increment timestamp: ts = 3
• Update frequency: cnt[4] = 2
• Add to heap: heappush(q, (-2, -3, 4))
• State: cnt = {4: 2, 5: 1}, q = [(-2, -3, 4), (-1, -2, 5), (-1, -1, 4)]
  • The heap now has 4 at the top (frequency 2 beats frequency 1)

Step 4: push(6)

• Increment timestamp: ts = 4
• Update frequency: cnt[6] = 1
• Add to heap: heappush(q, (-1, -4, 6))
• State: cnt = {4: 2, 5: 1, 6: 1}, heap has 4 with frequency 2 at top

Step 5: push(5)

• Increment timestamp: ts = 5
• Update frequency: cnt[5] = 2
• Add to heap: heappush(q, (-2, -5, 5))
• State: cnt = {4: 2, 5: 2, 6: 1}, heap has 5 with (-2, -5) at top
  • Both 4 and 5 have frequency 2, but 5 was pushed more recently

Step 6: push(4)

• Increment timestamp: ts = 6
• Update frequency: cnt[4] = 3
• Add to heap: heappush(q, (-3, -6, 4))
• State: cnt = {4: 3, 5: 2, 6: 1}, heap has 4 with frequency 3 at top

Step 7: pop()

• Extract from heap: heappop(q) returns (-3, -6, 4), so val = 4
• Decrement frequency: cnt[4] = 2
• Return: 4
• State: cnt = {4: 2, 5: 2, 6: 1}
  • Note: Old entries for 4 with frequencies 1 and 2 still exist in heap but are now outdated

Step 8: pop()

• Extract from heap: Top is (-2, -5, 5) (5 with frequency 2, timestamp 5)
  • This beats (-2, -3, 4) (4 with frequency 2, timestamp 3) because 5 is more recent
• Pop returns val = 5
• Decrement frequency: cnt[5] = 1
• Return: 5

The key observation is that the heap maintains all historical entries, but the combination of frequency and timestamp ensures we always get the correct element. The outdated entries (like the old frequency-1 entry for 4) never interfere because newer entries with higher frequencies naturally take priority.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(): O(1) - Initializing empty data structures takes constant time.
• push(val): O(log n) - Incrementing the counter and timestamp are O(1) operations, but inserting into the heap using heappush takes O(log n) time where n is the number of elements in the heap.
• pop(): O(log n) - Removing the top element from the heap using heappop takes O(log n) time, and decrementing the counter is O(1).

Space Complexity:

• O(n) where n is the total number of push operations performed.
• The heap q stores one entry for each push operation, never removing entries until they are popped, so it can grow up to size n.
• The counter dictionary cnt stores at most O(m) entries where m is the number of unique values pushed, which is bounded by n.
• The timestamp variable ts uses O(1) space.
• Overall space complexity is O(n) as the heap dominates the space usage.

Note: The heap stores tuples of (-frequency, -timestamp, value) using negative values to achieve max-heap behavior since Python's heapq implements a min-heap. This ensures elements with higher frequency are popped first, and among elements with the same frequency, the most recently pushed element (larger timestamp) is popped first.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Heap Pollution with Stale Entries

The Problem: The current implementation never removes outdated entries from the heap. Each time an element is pushed, a new entry is added to the heap with its current frequency, but when we pop an element and decrease its frequency, the old heap entries with higher frequencies remain. Over time, this leads to:

• Memory bloat as the heap grows unbounded
• Potential confusion when debugging, as the heap contains many "ghost" entries
• In extreme cases with many operations, this could cause memory issues

Example Scenario:

fs = FreqStack()
# Push the same element 1000 times
for _ in range(1000):
    fs.push(5)
# Now heap has 1000 entries for element 5 with frequencies 1, 2, 3, ..., 1000

# Pop element 5 once
fs.pop()  # Returns 5, frequency becomes 999
# But heap still contains the entry (-1000, timestamp, 5) which is now invalid

Solution Approach 1: Lazy Validation Instead of cleaning the heap, validate entries when popping:

def pop(self) -> int:
    """
    Pop with validation to handle stale entries in the heap.
    """
    while self.priority_queue:
        neg_freq, neg_ts, value = heappop(self.priority_queue)
        actual_freq = self.frequency_count[value]
      
        # Check if this entry is still valid (frequency matches current count)
        if -neg_freq == actual_freq and actual_freq > 0:
            # Valid entry - decrease frequency and return
            self.frequency_count[value] -= 1
            return value
        # Otherwise, this is a stale entry - continue to next
  
    # Should not reach here if used correctly
    raise IndexError("pop from empty FreqStack")

Solution Approach 2: Frequency Group Stacks A cleaner alternative design that avoids heap pollution entirely:

class FreqStack:
    def __init__(self):
        self.freq = {}  # element -> frequency
        self.group = defaultdict(list)  # frequency -> stack of elements
        self.max_freq = 0
  
    def push(self, val: int) -> None:
        freq = self.freq.get(val, 0) + 1
        self.freq[val] = freq
        self.group[freq].append(val)
        self.max_freq = max(self.max_freq, freq)
  
    def pop(self) -> int:
        val = self.group[self.max_freq].pop()
        self.freq[val] -= 1
        if not self.group[self.max_freq]:
            self.max_freq -= 1
        return val

Pitfall 2: Integer Overflow with Timestamps

The Problem: The timestamp counter continuously increments with each push operation. In a long-running application with millions of operations, this could theoretically overflow (though Python handles arbitrary precision integers, in other languages this would be a concern).

Solution: Use a relative ordering mechanism or periodically rebuild the heap when it gets too large:

def push(self, val: int) -> None:
    # Rebuild heap if it gets too polluted
    if len(self.priority_queue) > 10 * len(self.frequency_count):
        self._rebuild_heap()
  
    self.timestamp += 1
    self.frequency_count[val] += 1
    heappush(self.priority_queue, 
            (-self.frequency_count[val], -self.timestamp, val))

def _rebuild_heap(self):
    """Rebuild heap with only valid entries to prevent unbounded growth."""
    new_heap = []
    seen = set()
  
    for neg_freq, neg_ts, val in self.priority_queue:
        if val not in seen and self.frequency_count[val] > 0:
            seen.add(val)
            new_heap.append((-self.frequency_count[val], neg_ts, val))
  
    self.priority_queue = new_heap
    heapify(self.priority_queue)