Sponsored
Sponsored
This approach uses a combination of hash maps and stacks. We keep a hash map to track the frequency of each element in the stack. Additionally, we use another hash map, where the key is the frequency and the value is a stack that stores elements with that frequency. This allows us to efficiently retrieve and remove the most frequent element.
Time Complexity: O(1) for both push and pop as it uses hashed or array operations.
Space Complexity: O(n), where n is the number of elements in the stack.
1class FreqStack:
2 def __init__(self):
3 self.freq = {}
4 self.group = {}
5 self.maxfreq = 0
6
7 def push(self, x: int) -> None:
8 f = self.freq.get(x, 0) + 1
9 self.freq[x] = f
10 if f > self.maxfreq:
11 self.maxfreq = f
12 if f not in self.group:
13 self.group[f] = []
14 self.group[f].append(x)
15
16 def pop(self) -> int:
17 x = self.group[self.maxfreq].pop()
18 self.freq[x] -= 1
19 if not self.group[self.maxfreq]:
20 self.maxfreq -= 1
21 return x
22The code uses two dictionaries: 'freq' keeps track of the frequency of each element, and 'group' maintains stacks of elements with the same frequency. The element is pushed into the stack corresponding to its frequency in 'group'. For popping, the element associated with the highest frequency is popped from the appropriate stack.
This approach employs a priority queue (heap) to manage elements based on their frequency and their occurrence order. Each element in the queue is represented as a tuple (negative frequency, order, element) to simulate a max-heap based on frequency, breaking ties using the order of elements.
Time Complexity: O(log n) for both push and pop due to heap operations.
Space Complexity: O(n), with n elements in the stack.
1import java.util.HashMap;
2import
This Java solution leverages a HashMap to count frequencies and a PriorityQueue to manage the ordering of elements by frequency and index. It ensures that the elements are popped in the order of their frequency priority and occurrence in case of a tie.