Maximum Frequency Stack
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.
class FreqStack {
// Map of element -> frequency
HashMap<Integer, Integer> freq;
// Map of frequency -> stack of elements with this frequency
HashMap<Integer, Stack<Integer>> m;
int maxFreq;
public FreqStack() {
freq = new HashMap<>();
m = new HashMap<>();
maxFreq = 0;
}
public void push(int x) {
int f = freq.getOrDefault(x, 0) + 1;
freq.put(x, f);
maxFreq = Math.max(maxFreq, f);
if (!m.containsKey(f))
m.put(f, new Stack<Integer>());
m.get(f).add(x);
}
// Remember that map of all the frequencies upto the maxFreq exists
// Because when we promote an element from freq to freq+1
// then we are not actually removing that element from that stack
public int pop() {
int x = m.get(maxFreq).pop();
freq.put(x, maxFreq - 1);
if (m.get(maxFreq).size() == 0)
maxFreq--;
return x;
}
}
Last updated