DevExCode

895. Maximum Frequency Stack

Hash TableStackDesignOrdered Set

Explanation

To solve this problem, we can maintain a frequency map to keep track of the frequencies of elements pushed onto the stack. Additionally, we need to maintain a stack of stacks where each stack represents elements of the same frequency. When pushing an element, we update its frequency in the frequency map and push it onto the corresponding stack in the stack of stacks. When popping, we find the element with the highest frequency by checking the top elements of all stacks in the stack of stacks. We then pop the element from both the stack of stacks and the frequency map.

Here's a step-by-step overview:

  1. Initialize the frequency map and the stack of stacks.
  2. When pushing an element, update its frequency in the frequency map and push it onto the corresponding stack in the stack of stacks.
  3. When popping, iterate over the stack of stacks to find the element with the highest frequency. Pop this element from the stack and update its frequency in the frequency map.

The time complexity of both push and pop operations is O(1) on average, as each operation involves updating the frequency map and the stack of stacks. The space complexity is O(n), where n is the total number of elements pushed onto the stack.

View Leetcode Problem
import java.util.*;

class FreqStack {
    Map<Integer, Integer> freqMap;
    Map<Integer, Stack<Integer>> freqStacks;
    int maxFreq;

    public FreqStack() {
        freqMap = new HashMap<>();
        freqStacks = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int val) {
        int freq = freqMap.getOrDefault(val, 0) + 1;
        freqMap.put(val, freq);
        maxFreq = Math.max(maxFreq, freq);

        freqStacks.computeIfAbsent(freq, k -> new Stack<>()).push(val);
    }

    public int pop() {
        int val = freqStacks.get(maxFreq).pop();
        freqMap.put(val, freqMap.get(val) - 1);

        if (freqStacks.get(maxFreq).isEmpty()) {
            maxFreq--;
        }

        return val;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

  • Add import statement if required.
  • Optimize the code for better time or space complexity.
  • Add test cases to validate edge cases and common scenarios.
  • Handle error conditions or invalid inputs gracefully.
  • Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Previous QuestionNext Question