Maximum Frequency Stack Solution in Java

Language Options

Problem Description

Welcome to the world of stacks, where the only thing that matters is how often you show up! The Maximum Frequency Stack problem on LeetCode is like a popularity contest for numbers. Imagine a party where everyone is trying to get noticed. The more you show up, the more popular you become!

In this problem, you need to implement a stack that supports the following operations:

push(val): Pushes an integer val onto the stack.
pop(): Removes and returns the most frequent element in the stack. If there is a tie, the element that was pushed most recently is removed.

So, if you have a stack of numbers and you keep pushing the same number, that number becomes the star of the show. But beware! If someone else shows up more often, they might just steal the spotlight!

Code Solution


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 count = new HashMap<>();
  private Map> countToStack = new HashMap<>();
}

Approach

The approach taken in this solution is quite clever. We maintain two maps:

count: This keeps track of how many times each number has been pushed onto the stack.
countToStack: This maps the frequency of numbers to a stack of numbers that have that frequency.

When we push a number, we update its count and push it onto the corresponding stack in countToStack. When popping, we simply retrieve the most frequent number from the stack and update its count accordingly. If the stack for the current maximum frequency becomes empty, we decrease the maximum frequency.

Time and Space Complexity

Time Complexity: O(1) for both push and pop operations, as we are using hash maps and deques for constant time access.

Space Complexity: O(n), where n is the number of unique elements pushed onto the stack, since we need to store counts and stacks for each unique element.

Real-World Example

Think of a coffee shop where customers order their favorite drinks. The more often a drink is ordered, the more likely it is to be featured on the menu. If a new drink suddenly becomes popular, it might just bump the old favorite off the list! This is exactly how the Maximum Frequency Stack works—keeping track of the most popular items and serving them first.