# Maximum Frequency Stack (MFS)

HARD

Implement a Maximum Frequency Stack (MFS), a class that simulates the operation of a stack-like data structure.

MFS has two functions:

• `push(int x)`: which pushes an integer x onto the stack.
• `pop()`: Which removes and returns the most frequent element in the stack. If there is a tie for the most frequent element, the element closest to the top of the stack is removed and returned.

Example:

```["MaximumFrequencyStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]

Output: [null,null,null,null,null,null,null,5,7,5,4]

Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.
Then:
pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].
pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].
pop() -> returns 5.
The stack becomes [5,7,4].
pop() -> returns 4.
The stack becomes [5,7].
```

We need to care about the frequency of an element. Let `frequencyByNumber` be a Map from x to the number of occurrences of x. Also, we need to track the most frequent element in the Stack as `maxFrequency`. This is clear because we must pop the element with the maximum frequency. The main question then becomes: among elements with the same (maximum) frequency, how do we know which element is most recent? We can use a stack to query this information: the top of the stack is the most recent. To this end, let the group be a map from frequency to a stack of elements with that frequency named as `numberListByFrequency`. We now have all the required components to implement `MaximumFrequencyStack`. Following is the implementation:

```import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class MaximumFrequencyStack {

private int maxFrequency = 0;
private Map<Integer, Integer> frequencyByNumber = null;
private Map<Integer, Stack<Integer>> numberListByFrequency = null;

public MaximumFrequencyStack() {
frequencyByNumber = new HashMap<>();
numberListByFrequency = new HashMap<>();
}

public void push(int x) {
int frequency = frequencyByNumber.getOrDefault(x, 0);
frequency = frequency + 1;
maxFrequency = Math.max(maxFrequency, frequency);
frequencyByNumber.put(x, frequency);
Stack<Integer> numberList = numberListByFrequency.get(frequency);
if (numberList == null) {
numberList = new Stack<>();
numberListByFrequency.put(frequency, numberList);
}
numberList.push(x);
}

public int pop() {
Stack<Integer> numberList = numberListByFrequency.get(maxFrequency);
int value = numberList.pop();
if (numberList.isEmpty()) {
maxFrequency--;
}
int frequency = frequencyByNumber.get(value);
frequency = frequency - 1;
if (frequency == 0) {
frequencyByNumber.remove(value);
} else {
frequencyByNumber.put(value, frequency);
}
return value;
}
}
```
• Time Complexity: O(1) for both `push` and `pop` operations.
• Space Complexity: O(N), where `N` is the number of elements in the `MaximumFrequencyStack`.

Categories: Stack