By Long Luo

This article is the solution HashMap Solution with Detailed Explanation of Problem 895. Maximum Frequency Stack.

Intuition

Let’s look at the problem description first.

1. \(\texttt{FreqStack()}\) constructs an empty frequency stack.
2. void \(\texttt{push(int val)}\) pushes an integer val onto the top of the stack.
3. int \(\texttt{pop()}\) removes and returns the most frequent element in the stack.
4. 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. We can use \(\texttt{HashMap}\) to record the frequency of each element.

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

The code is as follows.

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 the 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 \(\texttt{HashMap}\) combined with LinkedList, the time complexity of inserting and deleting is \(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

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;
    }
}

Analysis

• Time Complexity: \(O(1)\).
  • \(\texttt{push}\): \(O(1)\)
  • \(\texttt{pop}\): \(O(1)\)
• Space Complexity: \(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. 😉😃💗