LeetCode 895: Maximum Frequency Stack Solution

Master LeetCode problem 895 (Maximum Frequency Stack), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

895. Maximum Frequency Stack

Hard

Hash Table Stack Design Ordered Set

Problem Explanation

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:

Initialize the frequency map and the stack of stacks.
When pushing an element, update its frequency in the frequency map and push it onto the corresponding stack in the stack of stacks.
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.

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 895 (Maximum Frequency Stack)?

This page provides optimized solutions for LeetCode problem 895 (Maximum Frequency Stack) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 895 (Maximum Frequency Stack)?

The time complexity for LeetCode 895 (Maximum Frequency Stack) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 895 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 895 in Java, C++, or Python.

Back to LeetCode Solutions