895. Maximum Frequency Stack

HardStackDesignHash TableOrdered Set
Leetcode Link

Problem Description

The problem asks for the design of a special kind of stack that keeps track of the frequency of elements as they are pushed. Unlike a regular stack, which simply adds elements to the top and removes them from the top in a LIFO (Last In First Out) manner, this stack has the additional functionality of popping the most frequently occurring element. In case of a tie in frequency, the element closest to the top should be popped.

Intuition

To solve this problem, we must maintain a frequency map and a map for elements by frequency. For this, two hashmaps are used: one to count the instances (self.cnt) of each value and another (self.d) to store values grouped by their instance count. Additionally, we keep track of the maximum frequency (self.mx) among all elements in the stack at any given time.

  • When push is called, we increase the count of the element and update the element's group by frequency. We also update the self.mx to ensure it's always the highest frequency we've encountered so far.
  • Conversely, when pop is called, we need to retrieve and return the most frequent element, which is at the end of the list in the self.d dictionary for the maximum frequency. After removing the element, we decrease its count in self.cnt. Should the list for this frequency be empty afterward, it means we no longer have elements with this highest frequency, so we decrement self.mx.

The key to the solution is making sure that both push and pop operations are done in O(1) average time complexity, which is achieved through the use of the hashmaps and keeping track of the maximum frequency dynamically.

Learn more about Stack patterns.

Solution Approach

The implementation of the FreqStack utilizes hash maps, a commonly used data structure in algorithm design for achieving efficient, average O(1) time access and manipulation of data.

The FreqStack class is structured as follows:

  1. Initialization (__init__ method):

    • self.cnt: A defaultdict(int) which maps each value to its frequency of occurrence in the stack.
    • self.d: A defaultdict(list) which maps frequencies to a list of values that have that frequency.
    • self.mx: An integer keeping track of the current maximum frequency of any element in the FreqStack.

  2. Push Operation (push method):

    • Increment the frequency count of the value val being pushed in self.cnt.
    • Append val to the list in self.d that corresponds to this new frequency count.
    • Update self.mx to reflect the maximum frequency count if the frequency of val is the new maximum.

  3. Pop Operation (pop method):

    • Identify the value val that needs to be popped, which is the last element in the list at self.d[self.mx].
    • Pop this value from the list.
    • Decrement the frequency count of the value val in self.cnt.
    • If the list at the current maximum frequency is now empty, decrement self.mx as there are no longer any elements with this frequency.
    • Return the value val.

By using these structures, we can ensure that the push operation is conducted by simply incrementing the count and appending to a list, and the pop operation is a matter of popping from a list and updating counts. Both operations avoid any time-consuming searches or iterations, allowing for fast execution.

This approach elegantly handles the requirements of popping the most frequent element, and in the case of a tie, the element nearest to the top, all while maintaining average O(1) time complexity for both push and pop operations.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a scenario where we operate on a FreqStack object to illustrate the solution approach described above.

  1. Initialize the FreqStack object.:

    • self.cnt would be an empty defaultdict(int)
    • self.d would be an empty defaultdict(list)
    • self.mx would be initialized to 0, indicating no elements are in the stack yet

  2. Perform several push operations:

    • push(5): self.cnt[5] becomes 1 since 5 is now pushed once. self.d[1] now contains [5]. self.mx is updated to 1.
    • push(7): self.cnt[7] becomes 1. self.d[1] becomes [5, 7]. self.mx stays 1.
    • push(5): self.cnt[5] is incremented to 2. self.d[2] now has [5]. self.mx is updated to 2.
    • push(7): self.cnt[7] is incremented to 2. self.d[2] becomes [5, 7]. self.mx stays 2.
    • push(5): self.cnt[5] is incremented to 3. self.d[3] now has [5]. self.mx is updated to 3.

    At this point, our frequency map self.cnt looks like this: {5: 3, 7: 2} and our elements by frequency map self.d looks like this: {1: [5, 7], 2: [5, 7], 3: [5]}. The current maximum frequency self.mx is 3.

  3. Perform a pop operation:

    • We need to pop the most frequent element. According to self.mx, the most frequent elements are in the list self.d[3], which currently has [5].
    • We pop 5 from self.d[3], which then becomes an empty list. Now, self.cnt[5] is decremented to 2.
    • Since self.d[3] is empty, we decrement self.mx to 2.

    The popped element is 5. After the pop, the structures are:

    • self.cnt: {5: 2, 7: 2}
    • self.d: {1: [5, 7], 2: [5, 7]}
    • self.mx: 2

Continuing to push and pop using the same approach, the FreqStack will maintain the frequency of elements and allow us to pop the most frequent element quickly, or the latest pushed element among the most frequent when there's a tie, achieving the average O(1) time complexity for both operations.

Solution Implementation

1from collections import defaultdict
2
3class FreqStack:
4    def __init__(self):
5        # Initialize a dictionary to count the frequency of elements
6        self.freq_counter = defaultdict(int)
7        # A dictionary that maps frequencies to a list of elements with that frequency
8        self.freq_dict = defaultdict(list)
9        # Variable to keep track of the maximum frequency observed so far
10        self.max_freq = 0
11
12    def push(self, val: int) -> None:
13        """
14        Pushes an integer onto the stack and updates the structures tracking element frequency.
15        """
16        # Increment the frequency count for the given value
17        self.freq_counter[val] += 1
18        # Add the value to the list of values that have the new frequency count
19        self.freq_dict[self.freq_counter[val]].append(val)
20        # Update the maximum frequency if it's exceeded by this value's frequency
21        self.max_freq = max(self.max_freq, self.freq_counter[val])
22
23    def pop(self) -> int:
24        """
25        Pops and returns the most frequent integer from the stack. If there is a tie,
26        it returns the integer closest to the top of the stack.
27        """
28        # Pop the value from the list corresponding to the maximum frequency
29        val = self.freq_dict[self.max_freq].pop()
30        # Decrement the frequency count for that value
31        self.freq_counter[val] -= 1
32        # If there are no more elements with the current maximum frequency, decrease the maximum frequency
33        if not self.freq_dict[self.max_freq]:
34            self.max_freq -= 1
35        # Return the value
36        return val
37
38
39# How to use the FreqStack class
40# obj = FreqStack()
41# obj.push(val)
42# param_2 = obj.pop()
43
1import java.util.HashMap;
2import java.util.Map;
3import java.util.Deque;
4import java.util.ArrayDeque;
5
6// Class to define a stack-like data structure that supports push and pop 
7// operations based on the frequency of elements.
8class FreqStack {
9    // A map to store the frequency of each element.
10    private Map<Integer, Integer> frequencyMap = new HashMap<>();
11    // A map to store stacks corresponding to each frequency.
12    private Map<Integer, Deque<Integer>> frequencyStackMap = new HashMap<>();
13    // Variable to store the current maximum frequency.
14    private int maxFrequency;
15
16    // Constructor for the FreqStack class.
17    public FreqStack() {
18        // Initialize the maxFrequency to 0.
19        maxFrequency = 0;
20    }
21
22    // Method to push an integer onto the stack.
23    public void push(int val) {
24        // Increase the frequency of the value by 1.
25        frequencyMap.put(val, frequencyMap.getOrDefault(val, 0) + 1);
26        // Get the updated frequency of the value.
27        int currentFrequency = frequencyMap.get(val);
28        // Add the value to the stack corresponding to its frequency.
29        frequencyStackMap.computeIfAbsent(currentFrequency, k -> new ArrayDeque<>()).push(val);
30        // Update the maxFrequency if necessary.
31        maxFrequency = Math.max(maxFrequency, currentFrequency);
32    }
33
34    // Method to pop and return the most frequent element from the stack.
35    // If there is a tie, it returns the element closest to the stack's top.
36    public int pop() {
37        // Pop the element from the stack with the maximum frequency.
38        int value = frequencyStackMap.get(maxFrequency).pop();
39        // Decrement the frequency count of the popped element.
40        frequencyMap.put(value, frequencyMap.get(value) - 1);
41        // If the stack corresponding to the maximum frequency is empty,
42        // then reduce the maximum frequency.
43        if (frequencyStackMap.get(maxFrequency).isEmpty()) {
44            maxFrequency--;
45        }
46        // Return the popped element.
47        return value;
48    }
49}
50
51/**
52 * The FreqStack class is used like this:
53 * FreqStack obj = new FreqStack();
54 * obj.push(val);
55 * int param_2 = obj.pop();
56 */
57
1#include <unordered_map>
2#include <stack>
3#include <algorithm>
4using namespace std;
5
6class FreqStack {
7public:
8    FreqStack() {
9        // Constructor initializes the FreqStack object.
10    }
11
12    void push(int val) {
13        // Increment the frequency count of the pushed value.
14        frequencyMap[val]++;
15      
16        // Push the value into the corresponding frequency stack.
17        frequencyStackMap[frequencyMap[val]].push(val);
18      
19        // Update the maximum frequency.
20        maxFrequency = max(maxFrequency, frequencyMap[val]);
21    }
22
23    int pop() {
24        // Get the value from the top of the maximum frequency stack and 
25        // pop it from the stack.
26        int value = frequencyStackMap[maxFrequency].top();
27        frequencyStackMap[maxFrequency].pop();
28      
29        // Decrement the frequency count of the popped value.
30        frequencyMap[value]--;
31      
32        // If the current maximum frequency stack is empty, decrement the 
33        // maximum frequency.
34        if (frequencyStackMap[maxFrequency].empty()) {
35            maxFrequency--;
36        }
37      
38        // Return the popped value.
39        return value;
40    }
41
42private:
43    unordered_map<int, int> frequencyMap; // Maps value to its frequency.
44    unordered_map<int, stack<int>> frequencyStackMap; // Maps frequency to a stack containing values with that frequency.
45    int maxFrequency = 0; // The current maximum frequency among all values.
46};
47
48/**
49 * The FreqStack object is instantiated and used as shown below:
50 * FreqStack* obj = new FreqStack();
51 * obj->push(val); // Pushes an element onto the stack.
52 * int param_2 = obj->pop(); // Pops and returns the most frequent element. If there is a tie, it returns the element closest to the stack's top.
53 */
54
1// Importing the necessary data structures from JavaScript's standard library
2import { Stack } from 'stack-typescript';
3
4// Define a global variable to track the frequency of each value.
5const frequencyMap: Record<number, number> = {};
6
7// Define a global variable to map frequencies to stacks that hold values with those frequencies.
8const frequencyStackMap: Record<number, Stack<number>> = {};
9
10// Define a global variable to keep track of the current maximum frequency.
11let maxFrequency: number = 0;
12
13// Initializes the global data structures.
14function initializeFreqStack(): void {
15  // Reset frequencyMap and frequencyStackMap for a new FreqStack instance. 
16  for (const key in frequencyMap) delete frequencyMap[key];
17  for (const key in frequencyStackMap) delete frequencyStackMap[key];
18  maxFrequency = 0;
19}
20
21// Defines the push method to add a value to the FreqStack.
22function push(val: number): void {
23  // Check if the value is already in frequencyMap, increment its count, otherwise add it with a count of 1.
24  frequencyMap[val] = (frequencyMap[val] || 0) + 1;
25
26  // If frequencyStackMap doesn't already have a stack for the new frequency, create one.
27  const frequency = frequencyMap[val];
28  if (!frequencyStackMap[frequency]) {
29    frequencyStackMap[frequency] = new Stack<number>();
30  }
31
32  // Push the value onto the appropriate frequency stack.
33  frequencyStackMap[frequency].push(val);
34
35  // Update maxFrequency if necessary.
36  maxFrequency = Math.max(maxFrequency, frequency);
37}
38
39// Defines the pop method to remove and return the most frequent value from the FreqStack.
40function pop(): number {
41  // Retrieve the stack with the current max frequency.
42  const maxFreqStack = frequencyStackMap[maxFrequency];
43
44  // Pop the most frequent value from this stack.
45  const value = maxFreqStack.top();
46  maxFreqStack.pop();
47
48  // Decrease the frequency of the popped value in the frequencyMap.
49  frequencyMap[value] -= 1;
50
51  // If the max frequency stack is now empty, decrement maxFrequency.
52  if (maxFreqStack.size() === 0) {
53    delete frequencyStackMap[maxFrequency];
54    maxFrequency -= 1;
55  }
56
57  // Return the popped value.
58  return value;
59}
60
61// To mimic class instantiation with global scope we invoke initializeFreqStack to start.
62initializeFreqStack();
63

Time and Space Complexity

Time Complexity

  • __init__(): The time complexity is O(1) as it only initializes variables.

  • push(val): The time complexity is O(1). The operation increments a counter, appends a value to a list, and updates a maximum value. Each of these operations is constant time as it doesn't depend on the size of the data structure.

  • pop(): The time complexity is O(1). It pops a value from the list corresponding to the maximum frequency, decrements the counter for the value, and decreases the maximum frequency if necessary. These operations are all constant time since the pop operation removes the last element of the list which is a constant time operation.

Space Complexity

  • Overall space complexity for the FreqStack class is O(N), where N is the number of elements pushed into the stack. This is because the stack keeps track of all elements inserted, their counts, and the lists corresponding to each frequency.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More