895. Maximum Frequency Stack

Problem

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.

Problem Summary

Implement FreqStack, a class that simulates the operations of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes the integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack. If there is more than one most frequent element, it removes and returns the element closest to the top of the stack.

Solution Approach

FreqStack stores a frequency map and a map of groups with the same frequency. When pushing, dynamically maintain the frequency of x and update it into the group corresponding to that frequency. When popping, reduce the frequency in the frequency dictionary accordingly and update the corresponding frequency group.

Code

package leetcode

type FreqStack struct {
	freq    map[int]int
	group   map[int][]int
	maxfreq int
}

func Constructor895() FreqStack {
	hash := make(map[int]int)
	maxHash := make(map[int][]int)
	return FreqStack{freq: hash, group: maxHash}
}

func (this *FreqStack) Push(x int) {
	if _, ok := this.freq[x]; ok {
		this.freq[x]++
	} else {
		this.freq[x] = 1
	}
	f := this.freq[x]
	if f > this.maxfreq {
		this.maxfreq = f
	}

	this.group[f] = append(this.group[f], x)
}

func (this *FreqStack) Pop() int {
	tmp := this.group[this.maxfreq]
	x := tmp[len(tmp)-1]
	this.group[this.maxfreq] = this.group[this.maxfreq][:len(this.group[this.maxfreq])-1]
	this.freq[x]--
	if len(this.group[this.maxfreq]) == 0 {
		this.maxfreq--
	}
	return x
}

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