895. Maximum Frequency Stack

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