# 895. Maximum Frequency Stack

## Description

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

• FreqStack() constructs an empty frequency stack.
• void push(int val) pushes an integer val onto the top of the stack.
• int pop() removes and returns the most frequent element in the stack.
• If there is a tie for the most frequent element, the element closest to the stack's top 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
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].


Constraints:

• 0 <= val <= 109
• At most 2 * 104 calls will be made to push and pop.
• It is guaranteed that there will be at least one element in the stack before calling pop.

## Solutions

• 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();
*/

• class FreqStack {
public:
FreqStack() {
}

void push(int val) {
++cnt[val];
d[cnt[val]].push(val);
mx = max(mx, cnt[val]);
}

int pop() {
int val = d[mx].top();
--cnt[val];
d[mx].pop();
if (d[mx].empty()) --mx;
return val;
}

private:
unordered_map<int, int> cnt;
unordered_map<int, stack<int>> d;
int mx = 0;
};

/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack* obj = new FreqStack();
* obj->push(val);
* int param_2 = obj->pop();
*/

• 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()


• 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
}

/**
* Your FreqStack object will be instantiated and called as such:
* obj := Constructor();
* obj.Push(val);
* param_2 := obj.Pop();
*/