## DEV Community is a community of 641,972 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # Solution: Maximum Frequency Stack seanpgallivan
Fledgling software developer; the struggle is a Rational Approximation.
・4 min read

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

#### Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

Implement `FreqStack`, a class which simulates the operation of a stack-like data structure.

`FreqStack` has two functions:

• `push(int x)`, which pushes an integer `x` 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.

#### Examples:

Example 1:
Input: ["FreqStack","push","push","push","push",
"push","push","pop","pop","pop","pop"],
[[],,,,,,,[],[],[],[]]
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].

#### Constraints:

• Calls to `FreqStack.push(int x)` will be such that `0 <= 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 exceed `10000` in a single test case.
• The total number of `FreqStack.pop` calls will not exceed `10000` in a single test case.
• The total number of `FreqStack.push` and `FreqStack.pop` calls will not exceed `150000` across all test cases.

#### Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

There are many ways to solve this problem, but the description gives us two clues as to the most efficient way to do so. First, any time the word "frequency" is used, we're most likely going to need to make a frequency map. Second, they use the word "stack" in the title, so we should look at the possibility of a stack solution.

In this instance, we should consider a 2D stack, with frequency on one side and input order on the other. This stack will hold each individual instance of a value (x) pushed separately by what the frequency was at the time of insertion.

Frequency will work here because it starts at 1 and will increment from there. If we remember to pop off unused frequencies, then the top of the frequency dimension of our stack (stack[stack.length-1]) will always represent the most frequent element, while the top of the input order dimension will represent the most recently seen value.

Our frequency map (fmap) will be used to keep track of the current frequencies of seen elements, so we know where to enter new ones into our stack.

#### Implementation:

Since our frequencies are 1-indexed and the stack is 0-indexed, we have to insert a dummy 0-index for all languages except Javascript, which lets you directly access even undefined array elements by index.

#### Javascript Code:

(Jump to: Problem Description || Solution Idea)

``````class FreqStack  {
constructor() {
this.fmap = new Map()
this.stack = []
}

push(x) {
let freq = (this.fmap.get(x) || 0) + 1
this.fmap.set(x, freq)
if (!this.stack[freq]) this.stack[freq] = [x]
else this.stack[freq].push(x)
}

pop() {
let top = this.stack[this.stack.length-1], x = top.pop()
if (!top.length) this.stack.pop()
this.fmap.set(x, this.fmap.get(x) - 1)
return x
}
};
``````

#### Python Code:

(Jump to: Problem Description || Solution Idea)

``````class FreqStack:
def __init__(self):
self.fmap = Counter()
self.stack = 

def push(self, x: int) -> None:
self.fmap[x] += 1
freq = self.fmap[x]
if (freq == len(self.stack)): self.stack.append([x])
else: self.stack[freq].append(x)

def pop(self) -> int:
top = self.stack[-1]
x = top.pop()
if (not top): self.stack.pop()
self.fmap[x] -= 1
return x
``````

#### Java Code:

(Jump to: Problem Description || Solution Idea)

``````class FreqStack {
HashMap<Integer, Integer> fmap;
List<Stack<Integer>> stack;

public FreqStack() {
fmap = new HashMap();
stack = new ArrayList();
stack.add(new Stack());
}

public void push(int x) {
int freq = fmap.getOrDefault(x, 0) + 1;
fmap.put(x, freq);
if (freq == stack.size()) stack.add(new Stack());
stack.get(freq).add(x);
}

public int pop() {
Stack<Integer> top = stack.get(stack.size()-1);
int x = top.pop();
if (top.size() == 0) stack.remove(stack.size()-1);
fmap.put(x, fmap.get(x) - 1);
return x;
}
}
``````

#### C++ Code:

(Jump to: Problem Description || Solution Idea)

``````class FreqStack {
public:
unordered_map<int, int> fmap;
vector<vector<int>> fstack = {{}};

void push(int x) {
int freq = fmap[x] + 1;
fmap[x] = freq;
if (freq == fstack.size()) fstack.push_back(vector<int>());
fstack[freq].push_back(x);
}

int pop() {
int x = fstack.back().back();
fstack.back().pop_back();
if (fstack.back().empty()) fstack.pop_back();
fmap[x]--;
return x;
}
};
``````