Maximum Frequency Stack

Hard

Asked by:

+7

15 views

Topics:

Stacks

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.
- If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

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 <= 10⁹
At most 2 * 10⁴ calls will be made to push and pop.
It is guaranteed that there will be at least one element in the stack before calling pop.

Try coding it in LeetCode

Maximum Frequency Stack

Hard

Asked by:

+1

15 views

Topics:

Stacks

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.
- If there is a tie for the most frequent element, the element closest to the stack's top is removed and returned.

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 <= 10⁹
At most 2 * 10⁴ calls will be made to push and pop.
It is guaranteed that there will be at least one element in the stack before calling pop.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the elements being pushed onto the stack?
If multiple elements have the same maximum frequency, how should I resolve ties in the pop operation beyond considering the element closest to the top (e.g., is there any secondary tie-breaking criteria)?
Can I assume the `pop` method will only be called when the stack is non-empty?
What is the expected number of push and pop operations? This will help me understand performance considerations.
What data types should I use for tracking frequencies and elements in the stack?

Brute Force Solution

Approach

We want to simulate a stack that always returns the most frequent element. The brute force way means, for every request, we re-calculate everything from scratch. We won't be clever or save any work from before.

Here's how the algorithm would work step-by-step:

When we add a number, we simply put it on top of our stack.
When we need to find the most frequent number and remove it, we go through the entire stack (from bottom to top).
Count how many times each number appears in the entire stack.
Find the number that appears the most often.
If there are ties for the most frequent, find the one that's closest to the top of the stack.
Remove that number from the stack.
Give that number back as the answer.

Code Implementation

class FrequencyStack:

    def __init__(self):
        self.stack = []

    def push(self, value):
        self.stack.append(value)

    def pop(self):
        # Need to calculate frequencies for each pop
        frequency_counts = {}
        for number in self.stack:
            frequency_counts[number] = frequency_counts.get(number, 0) + 1

        maximum_frequency = 0
        for number in frequency_counts:
            maximum_frequency = max(maximum_frequency, frequency_counts[number])

        most_frequent_numbers = []
        for number in frequency_counts:
            if frequency_counts[number] == maximum_frequency:
                most_frequent_numbers.append(number)

        # Find the closest to the top
        index_to_remove = -1
        for i in range(len(self.stack) - 1, -1, -1):
            if self.stack[i] in most_frequent_numbers:
                index_to_remove = i
                # Pick the last one
                break

        # Store the value so that we can return it
        removed_value = self.stack[index_to_remove]

        # Modify the stack, removing the value we want
        self.stack.pop(index_to_remove)
        
        return removed_value

Big(O) Analysis

Time Complexity

O(n²) – The push operation has a time complexity of O(1) as it simply adds an element to the top of the stack. The pop operation, however, iterates through the entire stack to count the frequency of each element, which takes O(n) time. It then iterates through the stack again to find the element with the highest frequency that is closest to the top, which also takes O(n) time. Since the pop operation effectively involves two O(n) operations, and we perform at most n pop operations, the overall time complexity is O(n * (n + n)), which simplifies to O(n²).

Space Complexity

O(N) – The space complexity stems from counting the frequency of each number in the stack. In the worst-case scenario, we might need to store a count for each unique element in the stack, which could be N where N is the number of operations (push/pop) and thus the maximum size of the stack. We are also said to loop through the stack from bottom to top which implicitly creates a data structure that can hold up to N elements. This results in auxiliary space proportional to the input size, making the space complexity O(N).

Optimal Solution

Approach

The goal is to mimic a stack but prioritize elements that appear more frequently. We keep track of the frequency of each number and use that information to simulate popping from different stacks depending on the frequency.

Here's how the algorithm would work step-by-step:

Keep track of how many times each number has been pushed onto the stack.
Also, organize stacks of numbers based on their frequency. For instance, all numbers that have appeared once are in one stack, all that have appeared twice are in another stack, and so on.
When asked to push a number, increase its count and then place it onto the correct frequency-based stack.
When asked to pop, find the stack with the highest frequency numbers in it.
Pop the number from that stack. If there are multiple numbers in that stack, pick the most recently added one.
Decrease the count of the number that was popped and proceed.

Code Implementation

class FrequencyStack:

    def __init__(self):
        self.frequency_of_number = {}
        self.stacks_by_frequency = {}
        self.maximum_frequency = 0

    def push(self, number):
        frequency = self.frequency_of_number.get(number, 0) + 1
        self.frequency_of_number[number] = frequency

        # We need to update the maximum frequency
        self.maximum_frequency = max(self.maximum_frequency, frequency)

        if frequency not in self.stacks_by_frequency:
            self.stacks_by_frequency[frequency] = []
        self.stacks_by_frequency[frequency].append(number)

    def pop(self):
        #  Pop from the stack that contains the most frequent numbers
        number = self.stacks_by_frequency[self.maximum_frequency].pop()

        if not self.stacks_by_frequency[self.maximum_frequency]:
            self.maximum_frequency -= 1

        self.frequency_of_number[number] -= 1

        return number

Big(O) Analysis

Time Complexity

O(1) – The push operation involves incrementing the frequency of the number and adding it to the corresponding frequency stack, both of which are constant-time operations using hash maps and stacks. The pop operation involves retrieving the stack with the highest frequency, popping an element from it, and decrementing its frequency, all of which are also constant-time operations using hash maps and stacks. Therefore, both push and pop operations take O(1) time, irrespective of the number of push and pop calls, or the number of elements (n).

Space Complexity

O(N) – The algorithm uses a hash map to store the frequency of each number pushed onto the stack. In the worst case, all N numbers pushed are distinct, requiring O(N) space for the frequency map. Additionally, it uses a hash map of stacks, where each stack holds numbers of the same frequency; this also requires O(N) space in the worst case where the maximum frequency is proportional to N. Therefore, the overall auxiliary space complexity is O(N). Note N is the number of push operations.

Edge Cases

Case	How to Handle
Pushing and popping from an empty FreqStack	The frequencies and groups maps must be initialized correctly and the pop operation should gracefully handle an empty stack by possibly returning a specific value or throwing an exception.
Large number of push operations leading to significant memory usage	The implementation needs to consider the memory footprint of storing frequencies and groups of elements to avoid out-of-memory errors.
Extreme values of 'val' (very large positive or negative integers)	The solution should be robust enough to handle large integer values without causing integer overflows or other issues related to data type limits.
Popping from a stack where all elements have the same frequency	The stack should correctly pop the element closest to the top, following the LIFO principle in cases of equal frequency.
Pushing the same 'val' multiple times consecutively	The frequency counter should correctly increment and decrement even with repeated values, and the groups mapping should be updated accurately.
Interleaved push and pop operations resulting in complex frequency distributions	The frequency tracking and group management must be able to handle a variety of push/pop sequences without losing accuracy.
A pop operation when the stack is not empty, but the most frequent element has been completely removed	The frequency and group mappings need to be cleaned up appropriately during pops to prevent the algorithm from getting stuck or returning incorrect values after an element's frequency drops to zero.
Maximum number of operations performed leading to performance bottlenecks.	The time complexity of push and pop operations should be efficient enough to handle a large number of operations within a reasonable time frame using data structures like hash maps and stacks.