[Leetcode][895. Maximum Frequency Stack] 2-Steps to Master the HashMap Solution with Detailed Explanation

By Long Luo

This article is the solution of Problem 895. Maximum Frequency Stack.

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
30
31
32
33
34
35
36
37
38
895. Maximum Frequency Stack

Hard

Design a stack-like data structure to push elements to the stack and pop the most frequent element from 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 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
FreqStack freqStack = new FreqStack();
freqStack.push(5); // The stack is [5]
freqStack.push(7); // The stack is [5,7]
freqStack.push(5); // The stack is [5,7,5]
freqStack.push(7); // The stack is [5,7,5,7]
freqStack.push(4); // The stack is [5,7,5,7,4]
freqStack.push(5); // The stack is [5,7,5,7,4,5]
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4].
freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4].
freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4].
freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].

Constraints:
0 <= val <= 10^9
At most 2 * 10^4 calls will be made to push and pop.
It is guaranteed that there will be at least one element in the stack before calling pop.

First, let’s look at the problem description:

FreqStack()\texttt{FreqStack()} constructs an empty frequency stack.

  1. void push(int val)\texttt{push(int val)} pushes an integer val onto the top of the stack.
  2. int pop()\texttt{pop()} removes and returns the most frequent element in the stack.
  3. If there is a tie for the most frequent element, the element closest to the stack’s top is removed and returned.

The requirements of the problems can be listed in 3 rules:

  1. Pop the stack by the max frequency;
  2. Among all the elements with the same (maximum) frequency, pop the element closest to the stack’s top.

To simplify the problem, let’s just ignore rule 2 for now, it looks easier.

Step 1

We care more about the frequency of the elements. Let freq be a Map of occurrences of xx to xx.

Additionally, we also care about maxfreq, the current maximum frequency of any element in the stack. we use maxFreq\textit{maxFreq} to store the maximum frequency.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class FreqStack_map {
Map<Integer, Integer> freqMap;
int maxFreq = 0;

public FreqStack_map() {
freqMap = new HashMap<>();
maxFreq = 0;
}

public void push(int val) {
int freq = freqMap.getOrDefault(val, 0) + 1;
freqMap.put(val, freq);
if (freq > maxFreq) {
maxFreq = freq;
}
}

public int pop() {
int ret = freqMap.get(maxFreq);
freqMap.put(ret, freqMap.get(ret) - 1);
maxFreq--;
return ret;
}
}

This solution has a problem. If elements with the same frequency, how to judge which element is the newest?

Step 2

How to know the order of elements with the same frequency?

We can use the stack to query this information: elements near the top of the stack are always newer.

We consider the elements with the same frequency are groups. In a group, elements were stored in the stack.

Using HashMap combined with LinkedList, the time complexity of inserting and deleting is O(1)O(1).

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
30
31
32
33
34
35
36
37
38
39
class FreqStack {
Map<Integer, Integer> freqMap;
Map<Integer, LinkedList<Integer>> groupFreqMap;
int maxFreq = 0;

public FreqStack() {
freqMap = new HashMap<>();
groupFreqMap = new HashMap<>();
}

public void push(int val) {
int freq = freqMap.getOrDefault(val, 0) + 1;
freqMap.put(val, freq);
if (freq > maxFreq) {
maxFreq = freq;
}

groupFreqMap.putIfAbsent(freq, new LinkedList<>());
groupFreqMap.get(freq).push(val);
}

public int pop() {
int res = groupFreqMap.get(maxFreq).pop();
freqMap.put(res, freqMap.get(res) - 1);
if (groupFreqMap.get(maxFreq).isEmpty()) {
groupFreqMap.remove(maxFreq);
maxFreq--;
}

return res;
}
}

/**
* Your FreqStack object will be instantiated and called as such:
* FreqStack obj = new FreqStack();
* obj.push(val);
* int param_2 = obj.pop();
*/

Analysis

  • Time Complexity: O(N)O(N)
  • Space Complexity: O(N)O(N)

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗