Welcome to Subscribe On Youtube

895. Maximum Frequency Stack

Description

Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.

Implement the FreqStack class:

• FreqStack() constructs an empty frequency stack.
• void push(int val) pushes an integer val onto the top of the stack.
• int pop() removes and returns the most frequent element in the stack.
  • If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

 

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
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop();   // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop();   // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop();   // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

 

Constraints:

• 0 <= val <= 109
• At most 2 * 104 calls will be made to push and pop.
• It is guaranteed that there will be at least one element in the stack before calling pop.

Solutions

• Java
• C++
• Python
• Go

• class FreqStack {
      private Map<Integer, Integer> cnt = new HashMap<>();
      private Map<Integer, Deque<Integer>> d = new HashMap<>();
      private int mx;
  
      public FreqStack() {
      }
  
      public void push(int val) {
          cnt.put(val, cnt.getOrDefault(val, 0) + 1);
          int t = cnt.get(val);
          d.computeIfAbsent(t, k -> new ArrayDeque<>()).push(val);
          mx = Math.max(mx, t);
      }
  
      public int pop() {
          int val = d.get(mx).pop();
          cnt.put(val, cnt.get(val) - 1);
          if (d.get(mx).isEmpty()) {
              --mx;
          }
          return val;
      }
  }
  
  /**
   * Your FreqStack object will be instantiated and called as such:
   * FreqStack obj = new FreqStack();
   * obj.push(val);
   * int param_2 = obj.pop();
   */
  

• class FreqStack {
  public:
      FreqStack() {
      }
  
      void push(int val) {
          ++cnt[val];
          d[cnt[val]].push(val);
          mx = max(mx, cnt[val]);
      }
  
      int pop() {
          int val = d[mx].top();
          --cnt[val];
          d[mx].pop();
          if (d[mx].empty()) --mx;
          return val;
      }
  
  private:
      unordered_map<int, int> cnt;
      unordered_map<int, stack<int>> d;
      int mx = 0;
  };
  
  /**
   * Your FreqStack object will be instantiated and called as such:
   * FreqStack* obj = new FreqStack();
   * obj->push(val);
   * int param_2 = obj->pop();
   */
  

• class FreqStack:
      def __init__(self):
          self.cnt = defaultdict(int)
          self.d = defaultdict(list)
          self.mx = 0
  
      def push(self, val: int) -> None:
          self.cnt[val] += 1
          self.d[self.cnt[val]].append(val)
          self.mx = max(self.mx, self.cnt[val])
  
      def pop(self) -> int:
          val = self.d[self.mx].pop()
          self.cnt[val] -= 1
          if not self.d[self.mx]:
              self.mx -= 1
          return val
  
  
  # Your FreqStack object will be instantiated and called as such:
  # obj = FreqStack()
  # obj.push(val)
  # param_2 = obj.pop()
  
  

• type FreqStack struct {
  	cnt map[int]int
  	d   map[int][]int
  	mx  int
  }
  
  func Constructor() FreqStack {
  	return FreqStack{map[int]int{}, map[int][]int{}, 0}
  }
  
  func (this *FreqStack) Push(val int) {
  	this.cnt[val]++
  	this.d[this.cnt[val]] = append(this.d[this.cnt[val]], val)
  	this.mx = max(this.mx, this.cnt[val])
  }
  
  func (this *FreqStack) Pop() int {
  	val := this.d[this.mx][len(this.d[this.mx])-1]
  	this.d[this.mx] = this.d[this.mx][:len(this.d[this.mx])-1]
  	this.cnt[val]--
  	if len(this.d[this.mx]) == 0 {
  		this.mx--
  	}
  	return val
  }
  
  /**
   * Your FreqStack object will be instantiated and called as such:
   * obj := Constructor();
   * obj.Push(val);
   * param_2 := obj.Pop();
   */
  

All Problems

All Solutions