Maximum Frequency Stack

Data Structures and Algorithms

Statement

Implement a FrequencyStack data structure with the following methods.

• constructor(): Used to create a FrequencyStack
• push(value): Used to push an element onto the top of the stack
• pop(): Used to remove and return the most frequent element in the stack

Constraints

• 0 ≤ value ≤ 10⁴

Solution

"""
production algorithm
"""

from collections import defaultdict


class FrequencyStack:
    def __init__(self):
        self.frequencies = defaultdict(int)
        self.stacks = []

    def push(self, value):
        """
        time complexity O(1)
        space complexity O(n)
        """
        self.frequencies[value] += 1
        if len(self.stacks) < self.frequencies[value]:
            self.stacks.append([])
        self.stacks[self.frequencies[value] - 1].append(value)

    def pop(self):
        """
        time complexity O(1)
        space complexity O(n)
        """
        value = self.stacks[-1].pop()
        if len(self.stacks[-1]) == 0:
            self.stacks.pop()
        self.frequencies[value] -= 1
        return value

    def __repr__(self):
        return str(self.stacks)

"""
unit tests
"""

from unittest import TestCase
from algorithms.counters.maximum_frequency_stack.frequency_stack import FrequencyStack


class FrequencyStackTestCase(TestCase):
    def test_push(self):
        # Given
        elements = [1, 3, 3, 5, 5, 5, 7, 7, 7, 7, 9, 9, 9, 9, 9]
        frequency_stack = FrequencyStack()

        # When
        [frequency_stack.push(element) for element in elements]
        actual = str(frequency_stack)

        # Then
        expected = str([[1, 3, 5, 7, 9], [3, 5, 7, 9], [5, 7, 9], [7, 9], [9]])
        self.assertEqual(actual, expected)

    def test_pop(self):
        # Given
        elements = [1, 3, 3, 5, 5, 5, 7, 7, 7, 7, 9, 9, 9, 9, 9]
        frequency_stack = FrequencyStack()
        [frequency_stack.push(element) for element in elements]

        # When
        actual = [frequency_stack.pop() for _ in range(len(elements))]

        # Then
        expected = [9, 9, 7, 9, 7, 5, 9, 7, 5, 3, 9, 7, 5, 3, 1]
        self.assertEqual(actual, expected)

Strategy

Counters.

Explanation

The constructor initializes a frequencies list that’s used to count the frequencies of elements, and a stacks list that’s used to hold the elements. For each index i of the stacks list, there’s a stack of elements that have at least i+1 frequency.

When push(value) is requested, the frequencies list and stacks list are updated. First, the frequency of the element is incremented. Let k be the new frequency of the element. If the stacks list doesn’t already have a stack of elements with at least k frequency, then append that stack to the stacks list. Then, without condition, push the element to the stack of elements with at least k frequency.

When pop() is requested, the last element of the last stack is popped, i.e. the most frequent element in the stack. Then, the frequency of the element is decremented. Finally, the element is returned from the function.

Time Complexity

Both push(value) and pop() operate with a constant number of steps. Therefore, the time complexity of both functions is O(1).

Space Complexity

The auxiliary space used by FrequencyStack is n, where n is the number of elements in FrequencyStack. Therefore, the auxiliary space complexity of the data structure is O(n).

Links

data_structures_algorithms/algorithms/counters/maximum_frequency_stack at main ·…