Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

895. Maximum Frequency Stack

Time: Constructor, push(val: int), pop(): $O(1)$

Space: $O(|\texttt{push(val: int)}| - O(|\texttt{pop()}|)$

			


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




			


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




			


class FreqStack:
  def __init__(self):
    self.maxFreq = 0
    self.count = Counter()
    self.countToStack = 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