Maximum Frequency Stack

Hard

Maximum Frequency Stack

Hard

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 integer values that will be pushed onto the stack?
If `pop` is called on an empty stack (no elements pushed yet), what should the return value be?
Are we expected to handle concurrent calls to `push` and `pop` from multiple threads?
Are there any memory constraints, given that we'll be storing frequency counts and stacks of elements?
If multiple elements have the same maximum frequency when `pop` is called, is the most recently pushed element with that frequency the one that must be returned?

Brute Force Solution

Approach

The Maximum Frequency Stack problem can be solved with a brute force approach by simulating every possible push and pop operation sequence. We would essentially keep track of the frequency of each number and then, at each pop, search through our simulated stack to find the most frequent element, prioritizing later occurrences if there's a tie.

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

For each 'push' operation, add the number to the end of our simulated stack.
Increment the frequency count for that number.
For each 'pop' operation, find the number in our stack that has the highest frequency.
If several numbers have the same highest frequency, find the one that was most recently added to the stack (i.e., the one closest to the end of the stack).
Remove this number from the stack and decrement its frequency count.
Return the removed number.

Code Implementation

class FrequencyStackBruteForce:
    def __init__(self):
        self.stack = []
        self.frequency = {}

    def push(self, value):
        self.stack.append(value)
        self.frequency[value] = self.frequency.get(value, 0) + 1

    def pop(self):
        # Find the most frequent element in stack
        maximumFrequency = 0
        for value in self.frequency:
            maximumFrequency = max(maximumFrequency, self.frequency[value])

        mostFrequentElement = None
        mostFrequentIndex = -1

        # Prioritize later occurrences in the stack
        for index in range(len(self.stack) - 1, -1, -1):
            if self.frequency[self.stack[index]] == maximumFrequency:
                mostFrequentElement = self.stack[index]
                mostFrequentIndex = index
                break

        # Remove element and decrement frequency
        if mostFrequentElement is not None:
            del self.stack[mostFrequentIndex]
            self.frequency[mostFrequentElement] -= 1
            if self.frequency[mostFrequentElement] == 0:
                del self.frequency[mostFrequentElement]

        return mostFrequentElement

Big(O) Analysis

Time Complexity

O(n²) – The 'push' operation takes O(1) time as it simply appends to a list and updates a frequency map. However, the 'pop' operation iterates through the entire stack (of size n in the worst case) to find the most frequent element. In the worst-case scenario, where we perform n pop operations, each requiring a full scan of a stack that can grow to size n, the overall time complexity is O(n*n), which simplifies to O(n²).

Space Complexity

O(N) – The brute force solution stores all pushed numbers in a simulated stack, which requires O(N) space, where N is the number of push operations. Additionally, the solution maintains a frequency count for each number, which, in the worst-case scenario (all numbers are unique), can also require O(N) space. Therefore, the auxiliary space used is primarily driven by the simulated stack and the frequency counts, both potentially growing linearly with the number of push operations. Thus, the space complexity is O(N).

Optimal Solution

Approach

The problem asks us to create a stack that keeps track of element frequencies. We want to efficiently retrieve the most frequent element when requested, behaving like a stack in other operations. The key idea is to use separate stacks for each frequency count to easily access the most recently pushed element of a given 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.
Organize the numbers that have the same frequency into separate stacks; so, for example, all numbers that appear twice are kept on a separate stack.
When a number is pushed onto the main stack, increase its count and add it to the frequency stack corresponding to its new count.
When popping, figure out what the highest frequency currently present is. Pop the last element that was added to the stack for that frequency.
Decrement the count of the element that was popped. If the count becomes zero, we don't need to keep track of it anymore.
Return the popped element.

Code Implementation

class FrequencyStack:

    def __init__(self):
        self.frequency = {}
        self.frequency_stacks = {}
        self.maximum_frequency = 0

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

        # Update maximum frequency seen so far
        self.maximum_frequency = max(self.maximum_frequency, element_frequency)

        if element_frequency not in self.frequency_stacks:
            self.frequency_stacks[element_frequency] = []

        self.frequency_stacks[element_frequency].append(value)

    def pop(self):
        # Get element from stack with highest frequency
        popped_element = self.frequency_stacks[self.maximum_frequency].pop()

        if not self.frequency_stacks[self.maximum_frequency]:
            # If stack is empty, decrement maximum frequency
            self.maximum_frequency -= 1

        self.frequency[popped_element] -= 1

        return popped_element

Big(O) Analysis

Time Complexity

O(1) – The push operation involves incrementing the frequency count of the pushed element and pushing it onto the appropriate frequency stack. This takes constant time. The pop operation involves finding the maximum frequency, popping from the corresponding stack, and decrementing the frequency count, all of which also take constant time. Since each operation (push and pop) is done in constant time regardless of the number of elements, the time complexity is O(1).

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 unique, requiring space proportional to N to store their frequencies. Additionally, the algorithm maintains stacks for each frequency, and in the worst case these stacks collectively could hold all N elements. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Pushing a very large number of elements	Ensure data structures (maps, stacks) scale efficiently to avoid memory issues or performance degradation by choosing appropriate data structures.
Popping from an empty stack	Return a predefined value (e.g., -1) or throw an exception to indicate an error state.
Multiple elements with the same maximum frequency	The solution needs to maintain a stack per frequency, so the most recently pushed element with the maximum frequency is returned first automatically.
Integer overflow when tracking frequency counts	Use appropriate data types (e.g., long) or handle overflow scenarios explicitly, or impose limits on input values.
Pushing and popping elements with negative values	The solution should correctly handle negative values without any special consideration as hash maps correctly support negative keys.
Pushing elements with frequency exceeding available memory	Impose reasonable limits on the maximum frequency or the number of elements to prevent memory exhaustion.
Alternating push and pop operations leading to frequent stack switching	Analyze if frequent stack switching can be optimized or if it's an inherent characteristic of the input sequence.
Pushing the same element repeatedly	The frequency counter will increment correctly, and stacks will update accordingly.