Maximum Frequency Stack

• Data Structure: Use a single List (like ArrayList in Java) to store the elements in the order they are pushed.
• push(val) operation:
  • Simply append the new element val to the end of the list.
• pop() operation:
  1. Create a temporary HashMap to calculate the frequency of every element currently in the list.
  2. Iterate through the list to populate the frequency map and find the maximum frequency (maxFreq).
  3. Iterate through the list backwards, from the last element to the first.
  4. For each element, check its frequency in the map. The first element encountered that has a frequency equal to maxFreq is the one to be popped.
  5. Remove this element from the list by its index.
  6. Return the removed element.

In this approach, we maintain the stack's elements in an ArrayList. When push(val) is called, we add val to the end of this list, which is an O(1) operation on average.

The pop() method is more complex. Since we need to pop the most frequent element, and in case of a tie, the one closest to the top, we must first determine the frequencies of all elements. We can do this by iterating through the entire list and using a HashMap to store counts. While doing so, we can also keep track of the maximum frequency seen so far. After this initial O(N) scan, we know the maxFreq. Now, to respect the tie-breaking rule (closest to the top), we must scan the list again, but this time from the end towards the beginning. The first element we find whose frequency matches maxFreq is our target. We then remove it from the list and return it. The removal from an ArrayList can also take O(N) time, making the overall pop operation quite slow.

1class FreqStack {2    List<Integer> stack;3 4    public FreqStack() {5        stack = new ArrayList<>();6    }7 8    public void push(int val) {9        stack.add(val);10    }11 12    public int pop() {13        if (stack.isEmpty()) {14            return -1; // Or throw an exception15        }16 17        Map<Integer, Integer> freqMap = new HashMap<>();18        int maxFreq = 0;19        for (int val : stack) {20            int newFreq = freqMap.getOrDefault(val, 0) + 1;21            freqMap.put(val, newFreq);22            maxFreq = Math.max(maxFreq, newFreq);23        }24 25        int valToPop = -1;26        int indexToPop = -1;27        for (int i = stack.size() - 1; i >= 0; i--) {28            int currentVal = stack.get(i);29            if (freqMap.get(currentVal) == maxFreq) {30                valToPop = currentVal;31                indexToPop = i;32                break;33            }34        }35 36        stack.remove(indexToPop);37        return valToPop;38    }39}

• Data Structures:
  • freqMap: A HashMap<Integer, Integer> to store the frequency of each element (element -> frequency).
  • group: A HashMap<Integer, Stack<Integer>> to group elements by their frequency (frequency -> Stack of elements).
  • maxFreq: An integer to keep track of the current maximum frequency.
• push(val) operation:
  1. Retrieve the current frequency of val from freqMap, increment it, and update the map.
  2. Update maxFreq to be the maximum of its current value and the new frequency of val.
  3. Access the group map with the new frequency as the key. Push val onto the stack found at that key. If no stack exists, create a new one first.
• pop() operation:
  1. Get the stack of elements associated with maxFreq from the group map.
  2. Pop the top element from this stack. This element is the most frequent and was the most recently pushed among all elements with that frequency.
  3. Decrement the frequency of the popped element in freqMap.
  4. If the stack for maxFreq becomes empty after the pop, it means there are no more elements with that frequency, so decrement maxFreq.
  5. Return the popped element.

To optimize the pop operation, we need to avoid the linear scans. We can achieve this by maintaining more state. We use two HashMaps and an integer variable:

1. freqMap: A HashMap<Integer, Integer> that maps each element to its current frequency. This allows O(1) lookup of any element's frequency.
2. group: A HashMap<Integer, Stack<Integer>>. This is the key data structure. It maps a frequency to a Stack of elements that have that frequency. For example, group.get(3) would give us a stack of all numbers that currently appear 3 times. The stack ensures that elements that reached this frequency later are on top.
3. maxFreq: An integer that tracks the current maximum frequency among all elements. This avoids the need to search for it.

How it works:

• push(val): We find the new frequency of val and update freqMap. We update maxFreq if necessary. Then, we push val onto the stack corresponding to its new frequency in the group map. All these are O(1) operations.
• pop(): We know the element to pop must have a frequency of maxFreq. We use group.get(maxFreq) to get the stack of such elements. The top of this stack is our target because it was the last one to achieve this frequency. We pop it, update its frequency in freqMap, and if the stack for maxFreq becomes empty, we decrement maxFreq. This is also an O(1) operation.

1class FreqStack {2    // Map to store frequency of each element3    Map<Integer, Integer> freqMap;4    // Map to group elements by their frequency. Each frequency maps to a stack.5    Map<Integer, Stack<Integer>> group;6    // Variable to track the maximum frequency encountered so far7    int maxFreq;8 9    public FreqStack() {10        freqMap = new HashMap<>();11        group = new HashMap<>();12        maxFreq = 0;13    }14 15    public void push(int val) {16        // Get current frequency and increment it17        int freq = freqMap.getOrDefault(val, 0) + 1;18        // Update the frequency map19        freqMap.put(val, freq);20 21        // Update the max frequency22        maxFreq = Math.max(maxFreq, freq);23 24        // Add the element to the stack corresponding to its new frequency25        group.computeIfAbsent(freq, k -> new Stack<>()).push(val);26    }27 28    public int pop() {29        // Get the stack of elements with the maximum frequency30        Stack<Integer> topStack = group.get(maxFreq);31        // Pop the most recently added element from this stack32        int val = topStack.pop();33 34        // Decrement the frequency of the popped element35        freqMap.put(val, freqMap.get(val) - 1);36 37        // If the stack for the max frequency becomes empty and there are still elements,38        // it means the new max frequency is one less.39        if (topStack.isEmpty()) {40            maxFreq--;41        }42 43        return val;44    }45}