**HARD**

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

**MFS **has two functions:

which pushes an integer x onto the stack.`push(int x)`

:Which`pop()`

:**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