Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/895.html
895. Maximum Frequency Stack
Level
Hard
Description
Implement FreqStack
, a class which simulates the operation of a stack-like data structure.
FreqStack
has two functions:
push(int x)
, which pushes an integerx
onto the stack.pop()
, which removes and returns the most frequent element in the stack.- If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.
Example 1:
Input:
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top. Then:
pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].
pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].
pop() -> returns 5.
The stack becomes [5,7,4].
pop() -> returns 4.
The stack becomes [5,7].
Note:
- Calls to
FreqStack.push(int x)
will be such that0 <= x <= 10^9
. - It is guaranteed that
FreqStack.pop()
won’t be called if the stack has zero elements. - The total number of
FreqStack.push
calls will not exceed10000
in a single test case. - The total number of
FreqStack.pop
calls will not exceed10000
in a single test case. - The total number of
FreqStack.push
andFreqStack.pop
calls will not exceed150000
across all test cases.
Solution
Maintain a stack stack
to store the elements. Also maintain two maps, which are numFrequencyMap
that stores each number’s frequency, and frequencySetMap
that stores each frequency and the numbers with the frequency. The map frequencySetMap
is a tree map.
For the constructor, initialize the stack and the two maps.
For method push(int x)
, push x
into stack
and update the frequency of x
in numFrequencyMap
. As for frequencySetMap
, add x
into the set with the updated frequency and remove x
from the set with the previous frequency.
For method pop()
, find the maximum key in frequencySetMap
to obtain the maximum frequency, which can be obtained using lastKey
method in tree map, and obtain the set with the maximum key, which contains the elements with the maximum frequency. The element to be removed is in the set. To obtain the element closest to the top of the stack, pop elements from the stack until the element at the top of the stack is in the set. Then pop the element out as the return value and push the other elements back into the stack. After the stack is updated, update the two maps. For numFrequencyMap
, update the popped values’ frequency, and remove the entry if the frequency becomes 0. For frequencySetMap
, remove the popped value from the previous frequency’s set and add the value into the new frequency’s set. If the previous frequency’s set becomes empty, remove the entry with the previous frequency from frequencySetMap
. Finally, return the popped value.
-
class FreqStack { Stack<Integer> stack; Map<Integer, Integer> numFrequencyMap; TreeMap<Integer, Set<Integer>> frequencySetMap; public FreqStack() { stack = new Stack<Integer>(); numFrequencyMap = new HashMap<Integer, Integer>(); frequencySetMap = new TreeMap<Integer, Set<Integer>>(); } public void push(int x) { stack.push(x); int frequency = numFrequencyMap.getOrDefault(x, 0) + 1; numFrequencyMap.put(x, frequency); Set<Integer> set = frequencySetMap.getOrDefault(frequency, new HashSet<Integer>()); set.add(x); frequencySetMap.put(frequency, set); if (frequency > 1) { int prevFrequency = frequency - 1; Set<Integer> prevFrequencySet = frequencySetMap.get(prevFrequency); prevFrequencySet.remove(x); frequencySetMap.put(prevFrequency, prevFrequencySet); } } public int pop() { Stack<Integer> tempStack = new Stack<Integer>(); int maxFrequency = frequencySetMap.lastKey(); Set<Integer> maxFrequencySet = frequencySetMap.get(maxFrequency); while (!stack.isEmpty() && !maxFrequencySet.contains(stack.peek())) tempStack.push(stack.pop()); if (!stack.isEmpty()) { int popValue = stack.pop(); maxFrequencySet.remove(popValue); if (maxFrequencySet.size() > 0) frequencySetMap.put(maxFrequency, maxFrequencySet); else frequencySetMap.remove(maxFrequency); int nextFrequency = maxFrequency - 1; if (nextFrequency > 0) { numFrequencyMap.put(popValue, nextFrequency); Set<Integer> nextFrequencySet = frequencySetMap.getOrDefault(nextFrequency, new HashSet<Integer>()); nextFrequencySet.add(popValue); frequencySetMap.put(nextFrequency, nextFrequencySet); } else numFrequencyMap.remove(popValue); while (!tempStack.isEmpty()) stack.push(tempStack.pop()); return popValue; } else return -1; } } /** * Your FreqStack object will be instantiated and called as such: * FreqStack obj = new FreqStack(); * obj.push(x); * int param_2 = obj.pop(); */ ############ class FreqStack { private Map<Integer, Integer> cnt = new HashMap<>(); private Map<Integer, Deque<Integer>> d = new HashMap<>(); private int mx; public FreqStack() { } public void push(int val) { cnt.put(val, cnt.getOrDefault(val, 0) + 1); int t = cnt.get(val); d.computeIfAbsent(t, k -> new ArrayDeque<>()).push(val); mx = Math.max(mx, t); } public int pop() { int val = d.get(mx).pop(); cnt.put(val, cnt.get(val) - 1); if (d.get(mx).isEmpty()) { --mx; } return val; } } /** * Your FreqStack object will be instantiated and called as such: * FreqStack obj = new FreqStack(); * obj.push(val); * int param_2 = obj.pop(); */
-
// OJ: https://leetcode.com/problems/maximum-frequency-stack/ // Time: O(1) for all // Space: O(N) class FreqStack { unordered_map<int, int> freq; // number -> frequency vector<vector<int>> v; // frequency -> stack of numbers public: FreqStack() {} void push(int val) { int f = freq[val]++; if (v.size() <= f) v.emplace_back(); v[f].push_back(val); } int pop() { int val = v.back().back(); v.back().pop_back(); --freq[val]; if (v.back().empty()) v.pop_back(); return val; } };
-
class FreqStack: def __init__(self): self.cnt = defaultdict(int) self.d = defaultdict(list) 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 # Your FreqStack object will be instantiated and called as such: # obj = FreqStack() # obj.push(val) # param_2 = obj.pop() ############ class FreqStack(object): def __init__(self): self.m = collections.defaultdict(int) self.q = [] self.index = 0 def push(self, x): """ :type x: int :rtype: void """ self.m[x] += 1 heapq.heappush(self.q, (-self.m[x], -self.index, x)) self.index += 1 def pop(self): """ :rtype: int """ val = heapq.heappop(self.q)[2] self.m[val] -= 1 return val # Your FreqStack object will be instantiated and called as such: # obj = FreqStack() # obj.push(x) # param_2 = obj.pop()
-
type FreqStack struct { cnt map[int]int d map[int][]int mx int } func Constructor() FreqStack { return FreqStack{map[int]int{}, map[int][]int{}, 0} } func (this *FreqStack) Push(val int) { this.cnt[val]++ this.d[this.cnt[val]] = append(this.d[this.cnt[val]], val) this.mx = max(this.mx, this.cnt[val]) } func (this *FreqStack) Pop() int { val := this.d[this.mx][len(this.d[this.mx])-1] this.d[this.mx] = this.d[this.mx][:len(this.d[this.mx])-1] this.cnt[val]-- if len(this.d[this.mx]) == 0 { this.mx-- } return val } func max(a, b int) int { if a > b { return a } return b } /** * Your FreqStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(val); * param_2 := obj.Pop(); */