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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s