Solution: Maximum Frequency Stack
Tags: algorithms, javascript, java, python
Published: 2021-02-28 13:29:12

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/maximum-frequency-stack/discuss/1086543).*

---

#### [Leetcode Problem #895 (*Hard*): Maximum Frequency Stack](https://leetcode.com/problems/maximum-frequency-stack/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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",<br>"push","push","pop","pop","pop","pop"],<br>[[],[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<br>is [5,7,5,7,4,5] from bottom to top.<br><br>Then:<br><br>pop() -> returns 5, as 5 is the most frequent.<br>The stack becomes [5,7,5,7,4].<br><br>pop() -> returns 7, as 5 and 7 is the most<br>frequent, but 7 is closest to the top.<br>The stack becomes [5,7,5,4].<br><br>pop() -> returns 5.<br>The stack becomes [5,7,4].<br><br>pop() -> returns 4.<br>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:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class FreqStack:
    def __init__(self):
        self.fmap = Counter()
        self.stack = [0]

    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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
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:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
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;
    }
};
```