_895. Maximum Frequency Stack.md

895. Maximum Frequency Stack

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 11, 2024

Last updated : July 11, 2024

---

Related Topics : Hash Table, Stack, Design, Ordered Set

Acceptance Rate : 66.6 %

---

Solutions

• h895 v1 Inefficient.py
• h895 v2 Efficient O(1).py
• h895 v3 Without max val tracking.java

Python

h895 v1 Inefficient.py

class FreqStack:

    def __init__(self):
        self.dt = {}
        self.cnter = 0

    def push(self, val: int) -> None:
        if val not in self.dt :
            self.dt[val] = [1, [self.cnter]]
        else :
            self.dt[val][0] += 1
            self.dt[val][1].append(self.cnter)
        self.cnter += 1

    def pop(self) -> int:
        out, freq, indx = -1, -1, -1

        for k, v in self.dt.items() :
            if v[0] > freq or (v[0] == freq and v[1][-1] > indx):
                freq = v[0]
                indx = v[1][-1]
                out = k

        self.dt[out][0] -= 1
        self.dt[out][1].pop()

        if self.dt[out][0] == 0 :
            self.dt.pop(out)

        return out


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()

h895 v2 Efficient O(1).py

class FreqStack:

    def __init__(self):
        self.val_freqs = defaultdict(int)
        self.freq_vals = defaultdict(list)
        self.maxx = 0

    def push(self, val: int) -> None:
        self.val_freqs[val] += 1
        self.maxx = max(self.maxx, self.val_freqs[val])
        self.freq_vals[self.val_freqs[val]].append(val)

    def pop(self) -> int:
        if not self.freq_vals[self.maxx] :
            self.maxx -= 1
        
        out = self.freq_vals[self.maxx].pop()
        self.val_freqs[out] -= 1
        return out


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()

Java

h895 v3 Without max val tracking.java

class FreqStack {
    private HashMap<Integer, Integer> _valFrequencyTracker;
    private Stack<Stack<Integer>> _frequencyValTracker;

    public FreqStack() {
        this._valFrequencyTracker = new HashMap<>();
        this._frequencyValTracker = new Stack<>();
    }
    
    public void push(int val) {
        _valFrequencyTracker.put(val, _valFrequencyTracker.getOrDefault(val, 0) + 1);

        if (_valFrequencyTracker.get(val) > _frequencyValTracker.size()) {
            _frequencyValTracker.push(new Stack<Integer>());
        }
        
        _frequencyValTracker.get(_valFrequencyTracker.get(val) - 1).push(val);
    }
    
    public int pop() {
        if (_frequencyValTracker.peek().isEmpty()) {
            _frequencyValTracker.pop();
        }

        int output = _frequencyValTracker.peek().pop();
        _valFrequencyTracker.put(output, _valFrequencyTracker.get(output) - 1);

        return output;
    }
}

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