Maximum Frequency Stack

Manas Sinha

Developer | Designer

By Manas | 28 February 2021

February LeetCoding Challenge 2021

Day 28

PROBLEM STATEMENT:

Implement FreqStack, a class which simulates the operation of a stack-like data structure.
FreqStack 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 most frequent element, the element closest to the top of the stack is removed and returned.

Example 1

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:
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].

Note:

Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
The total number of FreqStack.push calls will not exceed 10000 in a single test case.
The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

Explanation

One way to solve this problem is to have a heap that keeps the most frequent element on the top and if the frequency is same, it keeps the element which was pushed last at the top. But in this approach the time complexity to push an element will be O(Logn). Let’s see if we can do better.

Instead of heap, we simply maintain an array of stacks such that the stack at index i has all the elements with frequency i. We keep track of the maximum i and pop the top element from the stack at that index when ever there is any pop operation.

ALGORITHM:

Declare two hash tables, one that keeps track of the frequency of each unique element, other is the array of stacks. And a max_freq variable that keeps track of maximum frequency.
Whenever there is a call for push operation push the element x in the stack at position freq[x] + 1. This is because freq[x] is the frequency of x before the current push operation so after this call the frequency of x will increase by 1. Also update the max_freq variable
In case of pop, pop the top element of the stack at the index max_freq , reduce its frequency in the frequency table by 1 and return it.
If the stack at index max_freq is empty after popping the top element, reduce max_freq value by 1.

Time complexity for push : O(1)
Time complexity for pop : O(1)
Space complexity : O(n), since we are using extra hash tables.

code

C++

class FreqStack {
public:
    FreqStack() {
        max_freq = 0;
    }
    
    void push(int x) {
        stacks[++freq[x]].push(x);
        max_freq = max(max_freq,freq[x]);
    }
    
    int pop() {
        int res = stacks[max_freq].top();
        stacks[max_freq].pop();
        freq[res]--;
        if(stacks[max_freq].empty()) 
            max_freq--;
        return res;
    }

private:
    map<int,int> freq;
    map<int,stack<int>> stacks;
    int max_freq;
};

PYTHON

class FreqStack:

    def __init__(self):
        self.freq = collections.defaultdict(int)
        self.stacks = collections.defaultdict(list)
        self.max_freq = 0

    def push(self, x: int) -> None:
        self.freq[x] += 1
        self.stacks[self.freq[x]].append(x)
        self.max_freq = max(self.max_freq,self.freq[x])

    def pop(self) -> int:
        temp = self.stacks[self.max_freq].pop()
        self.freq[temp] -= 1
        
        if len(self.stacks[self.max_freq]) == 0:
            self.max_freq -= 1
        return temp
        


'''we are using defaultdict instead of normal python dict.
This is to ensure that we don't get a keyError beacause we are trying to access keys
which are not yet present in the dictionary.
defaultdict will assume that the default value of the key not yet present in the dictionary is zero'''

If you like the post leave a comment and share it.

Maximum Frequency Stack | February Leetcoding Challenge 2021 | Day 28

By Manas | 28 February 2021

February LeetCoding Challenge 2021

Day 28