Maximum Frequency Stack Leetcode Solution

Problem Statement

The Maximum Frequency Stack LeetCode Solution – “Maximum Frequency Stack” asks you to design a frequency stack in which whenever we pop an element from the stack, it should return the most frequent element present in the stack.

Implement the FreqStack class:

• FreqStack() constructs an empty frequency stack.
• void push(int val) pushes an integer val onto the top of the stack.
• int 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 stack’s top is removed and returned.

  


Example:

Input:  ["FreqStack", "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:

• Initialize the Empty Stack.
• After performing 6 times push operations, the elements of the stack are: [5, 7, 5, 7, 4, 5].
• The pop operation will yield the most frequent element present in the stack which is 5. Stack elements are: [5, 7, 5, 7, 4].
• The pop operation will yield the most frequent element present in the stack which is 7. Stack elements are: [5, 7, 5, 4].
• The pop operation will yield the most frequent element present in the stack which is 5. Stack elements are: [5, 7, 4].
• The pop operation will yield the most frequent element present in the stack which is 4. Stack elements are: [5, 7].

Approach

Idea:

1. The main idea to solve this problem is to use Hashing.
2. Maintain a global variable maximum frequency which will keep track of the maximum frequency found so far.
3. We’ll maintain a frequency table to store frequencies.
4. Maintain a stack of elements corresponding to each distinct frequency.
5. For each Push Operation:
   1. We’ll increment the frequency of the pushed element.
   2. We’ll update the maximum frequency if possible.
   3. Also, insert the element into a stack of elements corresponding to the current frequency.
6. For each Pop Operation:
   1. We’ll pop out the maximum frequency element.
   2. Also, pop out the element from the stack of frequencies.
   3. Decrement the frequency of the element and return the popped element.

Code

Maximum Frequency Stack Leetcode C++ Solution:

class FreqStack {
public:
    int maxfreq;
    unordered_map<int,int> freq;
    unordered_map<int,stack<int>> mp;
    void push(int val) {
        freq[val]++;
        mp[freq[val]].push(val);
        maxfreq = max(maxfreq,freq[val]);
    }
    int pop() {
        int val = mp[maxfreq].top();
        mp[maxfreq].pop();
        freq[val]--;
        if(mp[maxfreq].empty()){
            maxfreq--;
        }
        return val;
    }
};

Maximum Frequency Stack Leetcode Java Solution:

class FreqStack {
    int maxfreq;
    HashMap<Integer, Integer> freq = new HashMap<>();
    HashMap<Integer, Stack<Integer>> mp = new HashMap<>();
    public void push(int val) {
        int curr = freq.getOrDefault(val,0) + 1;
        freq.put(val,curr);
        maxfreq = Math.max(maxfreq,curr);
        if(!mp.containsKey(curr)){
            mp.put(curr,new Stack<Integer>());
        }
        mp.get(curr).add(val);
    }
    public int pop() {
        int val = mp.get(maxfreq).pop();
        freq.put(val,maxfreq-1);
        if(mp.get(maxfreq).size()==0){
            maxfreq--;
        }
        return val;
    }
}

Complexity Analysis for Maximum Frequency Stack Leetcode Solution

Time Complexity

The time complexity of the above code is O(1) if we use a good hash function that performs insertion and deletion operation in O(1) time average.

Space Complexity

The space complexity of the above code is O(N), N = maximum number of calls made to push function. We’re using a hashmap to keep integers and in the worst case, all the elements will be distinct which will take O(N) space to store the frequency of such elements.

Reference: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)