Formatted question description: https://leetcode.ca/all/895.html

895. Maximum Frequency Stack

Level

Hard

Description

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.

Solution

Maintain a stack stack to store the elements. Also maintain two maps, which are numFrequencyMap that stores each number’s frequency, and frequencySetMap that stores each frequency and the numbers with the frequency. The map frequencySetMap is a tree map.

For the constructor, initialize the stack and the two maps.

For method push(int x), push x into stack and update the frequency of x in numFrequencyMap. As for frequencySetMap, add x into the set with the updated frequency and remove x from the set with the previous frequency.

For method pop(), find the maximum key in frequencySetMap to obtain the maximum frequency, which can be obtained using lastKey method in tree map, and obtain the set with the maximum key, which contains the elements with the maximum frequency. The element to be removed is in the set. To obtain the element closest to the top of the stack, pop elements from the stack until the element at the top of the stack is in the set. Then pop the element out as the return value and push the other elements back into the stack. After the stack is updated, update the two maps. For numFrequencyMap, update the popped values’ frequency, and remove the entry if the frequency becomes 0. For frequencySetMap, remove the popped value from the previous frequency’s set and add the value into the new frequency’s set. If the previous frequency’s set becomes empty, remove the entry with the previous frequency from frequencySetMap. Finally, return the popped value.

class FreqStack {
    Stack<Integer> stack;
    Map<Integer, Integer> numFrequencyMap;
    TreeMap<Integer, Set<Integer>> frequencySetMap;

    public FreqStack() {
        stack = new Stack<Integer>();
        numFrequencyMap = new HashMap<Integer, Integer>();
        frequencySetMap = new TreeMap<Integer, Set<Integer>>();
    }
    
    public void push(int x) {
        stack.push(x);
        int frequency = numFrequencyMap.getOrDefault(x, 0) + 1;
        numFrequencyMap.put(x, frequency);
        Set<Integer> set = frequencySetMap.getOrDefault(frequency, new HashSet<Integer>());
        set.add(x);
        frequencySetMap.put(frequency, set);
        if (frequency > 1) {
            int prevFrequency = frequency - 1;
            Set<Integer> prevFrequencySet = frequencySetMap.get(prevFrequency);
            prevFrequencySet.remove(x);
            frequencySetMap.put(prevFrequency, prevFrequencySet);
        }
    }
    
    public int pop() {
        Stack<Integer> tempStack = new Stack<Integer>();
        int maxFrequency = frequencySetMap.lastKey();
        Set<Integer> maxFrequencySet = frequencySetMap.get(maxFrequency);
        while (!stack.isEmpty() && !maxFrequencySet.contains(stack.peek()))
            tempStack.push(stack.pop());
        if (!stack.isEmpty()) {
            int popValue = stack.pop();
            maxFrequencySet.remove(popValue);
            if (maxFrequencySet.size() > 0)
                frequencySetMap.put(maxFrequency, maxFrequencySet);
            else
                frequencySetMap.remove(maxFrequency);
            int nextFrequency = maxFrequency - 1;
            if (nextFrequency > 0) {
                numFrequencyMap.put(popValue, nextFrequency);
                Set<Integer> nextFrequencySet = frequencySetMap.getOrDefault(nextFrequency, new HashSet<Integer>());
                nextFrequencySet.add(popValue);
                frequencySetMap.put(nextFrequency, nextFrequencySet);
            } else
                numFrequencyMap.remove(popValue);
            while (!tempStack.isEmpty())
                stack.push(tempStack.pop());
            return popValue;
        } else
            return -1;
    }
}

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

############

class FreqStack {
    private Map<Integer, Integer> cnt = new HashMap<>();
    private Map<Integer, Deque<Integer>> d = new HashMap<>();
    private int mx;

    public FreqStack() {
    }

    public void push(int val) {
        cnt.put(val, cnt.getOrDefault(val, 0) + 1);
        int t = cnt.get(val);
        d.computeIfAbsent(t, k -> new ArrayDeque<>()).push(val);
        mx = Math.max(mx, t);
    }

    public int pop() {
        int val = d.get(mx).pop();
        cnt.put(val, cnt.get(val) - 1);
        if (d.get(mx).isEmpty()) {
            --mx;
        }
        return val;
    }
}

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

// OJ: https://leetcode.com/problems/maximum-frequency-stack/
// Time: O(1) for all
// Space: O(N)
class FreqStack {
    unordered_map<int, int> freq; // number -> frequency
    vector<vector<int>> v; // frequency -> stack of numbers
public:
    FreqStack() {}
    void push(int val) {
        int f = freq[val]++;
        if (v.size() <= f) v.emplace_back();
        v[f].push_back(val);
    }
    int pop() {
        int val = v.back().back();
        v.back().pop_back();
        --freq[val];
        if (v.back().empty()) v.pop_back();
        return val;
    }
};

class FreqStack:
    def __init__(self):
        self.cnt = defaultdict(int)
        self.d = defaultdict(list)
        self.mx = 0

    def push(self, val: int) -> None:
        self.cnt[val] += 1
        self.d[self.cnt[val]].append(val)
        self.mx = max(self.mx, self.cnt[val])

    def pop(self) -> int:
        val = self.d[self.mx].pop()
        self.cnt[val] -= 1
        if not self.d[self.mx]:
            self.mx -= 1
        return val


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(val)
# param_2 = obj.pop()

############

class FreqStack(object):

    def __init__(self):
        self.m = collections.defaultdict(int)
        self.q = []
        self.index = 0
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.m[x] += 1
        heapq.heappush(self.q, (-self.m[x], -self.index, x))
        self.index += 1

    def pop(self):
        """
        :rtype: int
        """
        val = heapq.heappop(self.q)[2]
        self.m[val] -= 1
        return val


# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()

type FreqStack struct {
	cnt map[int]int
	d   map[int][]int
	mx  int
}

func Constructor() FreqStack {
	return FreqStack{map[int]int{}, map[int][]int{}, 0}
}

func (this *FreqStack) Push(val int) {
	this.cnt[val]++
	this.d[this.cnt[val]] = append(this.d[this.cnt[val]], val)
	this.mx = max(this.mx, this.cnt[val])
}

func (this *FreqStack) Pop() int {
	val := this.d[this.mx][len(this.d[this.mx])-1]
	this.d[this.mx] = this.d[this.mx][:len(this.d[this.mx])-1]
	this.cnt[val]--
	if len(this.d[this.mx]) == 0 {
		this.mx--
	}
	return val
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * param_2 := obj.Pop();
 */

895 - Maximum Frequency Stack

895. Maximum Frequency Stack

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

895. Maximum Frequency Stack

Level

Description

Solution

All Problems

All Solutions