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.
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 <= 1092 * 104 calls will be made to push and pop.pop.This approach uses a combination of hash maps and stacks. We keep a hash map to track the frequency of each element in the stack. Additionally, we use another hash map, where the key is the frequency and the value is a stack that stores elements with that frequency. This allows us to efficiently retrieve and remove the most frequent element.
The code uses two dictionaries: 'freq' keeps track of the frequency of each element, and 'group' maintains stacks of elements with the same frequency. The element is pushed into the stack corresponding to its frequency in 'group'. For popping, the element associated with the highest frequency is popped from the appropriate stack.
JavaScript
Time Complexity: O(1) for both push and pop as it uses hashed or array operations.
Space Complexity: O(n), where n is the number of elements in the stack.
This approach employs a priority queue (heap) to manage elements based on their frequency and their occurrence order. Each element in the queue is represented as a tuple (negative frequency, order, element) to simulate a max-heap based on frequency, breaking ties using the order of elements.
This C++ implementation uses an unordered_map to maintain frequency counts and a priority queue to order elements by frequency and recency. The priority queue ensures that the most frequent, most recent element is always at the top, providing efficient pops.
Java
Time Complexity: O(log n) for both push and pop due to heap operations.
Space Complexity: O(n), with n elements in the stack.
| Approach | Complexity |
|---|---|
| Approach 1: Hash Map with Frequency Stacks | Time Complexity: O(1) for both push and pop as it uses hashed or array operations. |
| Approach 2: Priority Queue | Time Complexity: O(log n) for both push and pop due to heap operations. |
Design Min Stack - Amazon Interview Question - Leetcode 155 - Python • NeetCode • 255,349 views views
Watch 9 more video solutions →Practice Maximum Frequency Stack with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor