Solution Explanation: Maximum Frequency Stack

The problem requires designing a data structure that behaves like a stack but prioritizes popping the most frequent element. If multiple elements share the maximum frequency, the element pushed most recently should be popped.

Two main solutions are presented: one using a priority queue and another using hash tables.

Solution 1: Hash Table + Priority Queue

This approach uses a hash table (cnt) to store the frequency of each element and a priority queue (q) to manage elements based on frequency and push order.

Data Structures:

• cnt: A hash table (dictionary in Python) mapping element values to their frequencies.
• q: A priority queue (min-heap in Python, using heapq module). Elements are tuples (-frequency, -timestamp, value). The negative signs ensure the highest frequency and most recent timestamp are prioritized.
• ts: A timestamp counter to track the order of pushes.

Algorithm:

• push(val):
  1. Increment the timestamp (ts).
  2. Increment the frequency of val in cnt.
  3. Push (-cnt[val], -ts, val) onto the priority queue. The negative signs ensure that higher frequency and later timestamps have higher priority.
• pop():
  1. Pop the highest priority element (highest frequency, then most recent) from the priority queue.
  2. Decrement the frequency of the popped element in cnt.
  3. Return the popped element's value.

Time Complexity:

• push: O(log n), due to the priority queue insertion.
• pop: O(log n), due to the priority queue removal.

Space Complexity: O(n), to store the frequencies and the priority queue.

Solution 2: Double Hash Tables

This approach uses two hash tables to achieve O(1) time complexity for both push and pop operations.

Data Structures:

• cnt: A hash table mapping elements to their frequencies.
• d: A hash table mapping frequencies to stacks. Each stack stores the elements with that frequency.
• mx: An integer variable storing the maximum frequency currently present.

Algorithm:

• push(val):
  1. Increment val's frequency in cnt.
  2. Push val onto the stack associated with its frequency in d.
  3. Update mx if the new frequency is greater.
• pop():
  1. Pop the top element from the stack associated with mx in d. This is the most frequent, and most recently added element.
  2. Decrement the frequency of the popped element in cnt.
  3. If the stack associated with mx becomes empty, decrement mx.
  4. Return the popped element.

Time Complexity:

• push: O(1)
• pop: O(1)

Space Complexity: O(n)

Code Examples (Python):

Solution 1 (Priority Queue):

import heapq
from collections import defaultdict
 
class FreqStack:
    def __init__(self):
        self.cnt = defaultdict(int)
        self.q = []
        self.ts = 0
 
    def push(self, val: int) -> None:
        self.ts += 1
        self.cnt[val] += 1
        heapq.heappush(self.q, (-self.cnt[val], -self.ts, val))
 
    def pop(self) -> int:
        val = heapq.heappop(self.q)[2]
        self.cnt[val] -= 1
        return val

Solution 2 (Double Hash Tables):

from collections import defaultdict, deque
 
class FreqStack:
    def __init__(self):
        self.cnt = defaultdict(int)
        self.d = defaultdict(deque)
        self.mx = 0
 
    def push(self, val: int) -> None:
        self.cnt[val] += 1
        self.d[self.cnt[val]].append(val)
        self.mx = max(self.mx, self.cnt[val])
 
    def pop(self) -> int:
        val = self.d[self.mx].pop()
        self.cnt[val] -= 1
        if not self.d[self.mx]:
            self.mx -= 1
        return val

Solution 2 is generally preferred due to its superior time complexity. However, Solution 1 might be simpler to understand initially. The choice depends on the specific needs of your application. The code examples above are in Python, but similar implementations are possible in other languages like Java, C++, and Go.