
Problem Statement
The task is to design a specialized stack data structure, named FreqStack
, which extends the basic functionalities of a typical stack. FreqStack
supports standard push operations but has a unique feature for its pop operation. Unlike a regular stack that follows the Last-In-First-Out (LIFO) principle, the FreqStack
's pop operation removes the most frequently added element. If two or more elements have the same frequency, then the element closest to the top of the stack is removed.
This requires implementing both:
push(int val)
to add an element.pop()
to remove the element based on the stipulated conditions from the stack.
Examples
Example 1
Input:
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
Input Arguments:
[[], [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 are 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 are the most frequent, but 4 is closest to the top. The stack becomes [5,7]
Constraints
0 <= val <= 10^9
- At most
2 * 10^4
calls will be made topush
andpop
. - It is guaranteed that there will be at least one element in the stack before calling
pop
.
Approach and Intuition
In order to effectively manage the unique characteristics of FreqStack
, particularly the pop()
operation, here’s a structured approach:
Track Element Frequencies:
- Maintain a dictionary (
freq
) that stores the frequency of each element pushed onto the stack.
- Maintain a dictionary (
Maintain a Stack of Stacks Based on Frequencies:
- Use an additional dictionary (
group
) where each key corresponds to a frequency, and each value is a stack (or list) containing the elements that appear with that frequency. - This structure allows you to quickly retrieve the element with the highest frequency and preserve the order of insertion.
- Use an additional dictionary (
Implement
push(int val)
:- Increase the frequency of
val
in thefreq
dictionary. - Push
val
onto the corresponding stack ingroup[freq[val]]
. - Keep track of the current maximum frequency (
maxfreq
) seen so far.
- Increase the frequency of
Implement
pop()
:- Pop the element from the stack corresponding to
maxfreq
. - Decrease its frequency in
freq
. - If the stack for
maxfreq
becomes empty after popping, decrementmaxfreq
since there are no more elements at that frequency.
- Pop the element from the stack corresponding to
Efficiency:
- Both
push
andpop
operate in O(1) time on average due to the efficient use of dictionaries and stacks. - The design ensures that we always know the current most frequent element and can retrieve it in constant time.
- Both
Solutions
- Java
class FrequencyStack {
Map<Integer, Integer> frequency;
Map<Integer, Stack<Integer>> level;
int highestFrequency;
public FrequencyStack() {
frequency = new HashMap<>();
level = new HashMap<>();
highestFrequency = 0;
}
public void push(int x) {
int count = frequency.getOrDefault(x, 0) + 1;
frequency.put(x, count);
if (count > highestFrequency)
highestFrequency = count;
level.computeIfAbsent(count, z -> new Stack<>()).push(x);
}
public int pop() {
int x = level.get(highestFrequency).pop();
frequency.put(x, frequency.get(x) - 1);
if (level.get(highestFrequency).isEmpty())
highestFrequency--;
return x;
}
}
The provided Java solution implements a data structure known as a "Maximum Frequency Stack" which allows for efficient querying, insertion, and deletion based on the frequency of elements. The code utilizes two primary data structures:
- A
Map<Integer, Integer>
namedfrequency
to track the frequency of each element pushed into the stack. The key represents the element, and the value represents the frequency of that element in the stack. - A
Map<Integer, Stack<Integer>>
namedlevel
, where keys are frequencies and values are stacks that store elements with the corresponding frequency.
Explanation of the Methods:
Constructor
FrequencyStack()
: Initializes thefrequency
andlevel
maps and setshighestFrequency
to 0. This variable keeps track of the maximum frequency of any element in the stack at any given time.Method
push(int x)
:- Increments the frequency of the element
x
in thefrequency
map. - Updates
highestFrequency
if the frequency ofx
surpasses the currenthighestFrequency
. - Adds element
x
to the stack corresponding to its updated frequency in thelevel
map.
- Increments the frequency of the element
Method
pop()
:- Retrieves and removes the top element of the stack associated with
highestFrequency
. - Decrements the frequency of the popped element in the
frequency
map. - If the stack for the current
highestFrequency
becomes empty after the pop, decreaseshighestFrequency
by 1. - Returns the popped element.
- Retrieves and removes the top element of the stack associated with
This design ensures that push()
and pop()
operations are efficient, optimized for the scenario where quick access to the most frequently accessed elements is needed. The use of maps for frequency and grouping elements by their frequencies allows for fast lookups and adjustments, accommodating the stack's behavior which revolves around element frequency. The code is robust and handles edge cases such as popping when multiple elements have the same highest frequency.
No comments yet.