Skip to content

895. Maximum Frequency Stack 👍

  • Time:
    • Constructor: $O(1)$
    • push(val: int): $O(1)$
    • pop(): $O(1)$
  • Space: $O(|\texttt{push()}| - O(|\texttt{pop()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class FreqStack {
 public:
  void push(int val) {
    countToStack[++count[val]].push(val);
    maxFreq = max(maxFreq, count[val]);
  }

  int pop() {
    const int val = countToStack[maxFreq].top();
    countToStack[maxFreq].pop();
    --count[val];
    if (countToStack[maxFreq].empty())
      --maxFreq;
    return val;
  }

 private:
  int maxFreq = 0;
  unordered_map<int, int> count;
  unordered_map<int, stack<int>> countToStack;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class FreqStack {
  public void push(int val) {
    count.merge(val, 1, Integer::sum);
    countToStack.putIfAbsent(count.get(val), new ArrayDeque<>());
    countToStack.get(count.get(val)).push(val);
    maxFreq = Math.max(maxFreq, count.get(val));
  }

  public int pop() {
    final int val = countToStack.get(maxFreq).pop();
    count.merge(val, -1, Integer::sum);
    if (countToStack.get(maxFreq).isEmpty())
      --maxFreq;
    return val;
  }

  private int maxFreq = 0;
  private Map<Integer, Integer> count = new HashMap<>();
  private Map<Integer, Deque<Integer>> countToStack = new HashMap<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class FreqStack:
  def __init__(self):
    self.maxFreq = 0
    self.count = collections.Counter()
    self.countToStack = collections.defaultdict(list)

  def push(self, val: int) -> None:
    self.count[val] += 1
    self.countToStack[self.count[val]].append(val)
    self.maxFreq = max(self.maxFreq, self.count[val])

  def pop(self) -> int:
    val = self.countToStack[self.maxFreq].pop()
    self.count[val] -= 1
    if not self.countToStack[self.maxFreq]:
      self.maxFreq -= 1
    return val