Solution: Maximum Frequency Stack

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.

---

Leetcode Problem #895 (Hard): Maximum Frequency Stack

---

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"], [[],[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].

---

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 = [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:

(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;
    }
};