Design a Maximum Frequency Stack

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:

1 2	["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"], [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]

["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.

C++ Maximum Frequency Stack

We use a hash map i.e. unordered_map to store the frequencies of each number. We also need a variable to tell us the current maximum frequency. And, for each frequency, we need to be able to locate a stack which contains the same frequency elements and we can pop them in the stack order if we want.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class FreqStack {
public:
    FreqStack() {
        
    }
    
    void push(int x) {
        freq[x] ++;
        int f = freq[x];
        maxFreq = max(maxFreq, f);
        data[f].push(x);
    }
    
    int pop() {
        int x = data[maxFreq].top();
        data[maxFreq].pop();
        freq[x] --;
        if (data[maxFreq].empty()) {
            maxFreq --;
        }
        return x;
    }
private:
    int maxFreq = -1;
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> data;
};

class FreqStack {
public:
    FreqStack() {
        
    }
    
    void push(int x) {
        freq[x] ++;
        int f = freq[x];
        maxFreq = max(maxFreq, f);
        data[f].push(x);
    }
    
    int pop() {
        int x = data[maxFreq].top();
        data[maxFreq].pop();
        freq[x] --;
        if (data[maxFreq].empty()) {
            maxFreq --;
        }
        return x;
    }
private:
    int maxFreq = -1;
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> data;
};

Time complexity is O(1) constant, the space complexity is O(N).

Python Maximum Frequency Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class FreqStack(object):
    def __init__(self):
        self.freq = collections.Counter()
        self.group = collections.defaultdict(list)
        self.maxfreq = 0
 
    def push(self, x):
        f = self.freq[x] + 1
        self.freq[x] = f
        if f > self.maxfreq:
            self.maxfreq = f
        self.group[f].append(x)
 
    def pop(self):
        x = self.group[self.maxfreq].pop()
        self.freq[x] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return x

class FreqStack(object):
    def __init__(self):
        self.freq = collections.Counter()
        self.group = collections.defaultdict(list)
        self.maxfreq = 0

    def push(self, x):
        f = self.freq[x] + 1
        self.freq[x] = f
        if f > self.maxfreq:
            self.maxfreq = f
        self.group[f].append(x)

    def pop(self):
        x = self.group[self.maxfreq].pop()
        self.freq[x] -= 1
        if not self.group[self.maxfreq]:
            self.maxfreq -= 1
        return x

Java Maximum Frequency Stack Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class FreqStack {
    Map<Integer, Integer> freq;
    Map<Integer, Stack<Integer>> group;
    int maxfreq;
 
    public FreqStack() {
        freq = new HashMap();
        group = new HashMap();
        maxfreq = 0;
    }
 
    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        if (f > maxfreq) {
            maxfreq = f;
        }
        group.computeIfAbsent(f, z-> new Stack()).push(x);
    }
 
    public int pop() {
        int x = group.get(maxfreq).pop();
        freq.put(x, freq.get(x) - 1);
        if (group.get(maxfreq).size() == 0) {
            maxfreq--;
        }
        return x;
    }
}

class FreqStack {
    Map<Integer, Integer> freq;
    Map<Integer, Stack<Integer>> group;
    int maxfreq;

    public FreqStack() {
        freq = new HashMap();
        group = new HashMap();
        maxfreq = 0;
    }

    public void push(int x) {
        int f = freq.getOrDefault(x, 0) + 1;
        freq.put(x, f);
        if (f > maxfreq) {
            maxfreq = f;
        }
        group.computeIfAbsent(f, z-> new Stack()).push(x);
    }

    public int pop() {
        int x = group.get(maxfreq).pop();
        freq.put(x, freq.get(x) - 1);
        if (group.get(maxfreq).size() == 0) {
            maxfreq--;
        }
        return x;
    }
}

–EOF (The Ultimate Computing & Technology Blog) —