Maximum frequency stack implementation in java O(1)
Published in
2 min readAug 29, 2018
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 integerx
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 that0 <= 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 exceed10000
in a single test case. - The total number of
FreqStack.pop
calls will not exceed10000
in a single test case. - The total number of
FreqStack.push
andFreqStack.pop
calls will not exceed150000
across all test cases.
My JAVA implementation:
package leetcode;import java.util.HashMap;
import java.util.LinkedList;public class MaximumFrequencyStack {
public static void main(String[] args) {
MaximumFrequencyStack mfs = new MaximumFrequencyStack(); mfs.push(4);
mfs.push(0);
mfs.push(9);
mfs.push(3);
mfs.push(4);
mfs.push(2);
mfs.pop();
mfs.push(6);
mfs.pop();
mfs.push(1);
mfs.pop();
mfs.push(4);
mfs.pop();
mfs.pop();
mfs.pop();
mfs.pop();
mfs.pop();
mfs.pop();
} private LinkedList<Integer> queue;
private HashMap<Integer, Integer> counter;
private LinkedList<LinkedList<Integer>> frequencyAndItems;// it holds queue of element in the same frequency
int max = 0;
public MaximumFrequencyStack() {
queue = new LinkedList<>();
counter = new HashMap<>();
frequencyAndItems = new LinkedList<>();
LinkedList<Integer> init = new LinkedList<>();
init.add(Integer.MAX_VALUE);
frequencyAndItems.add(init); } public void push(int x) {
queue.add(x);
Integer count = counter.get(x);
if (count == null) {
count = 1;
counter.put(x, count);
} else {
count = count + 1;
counter.put(x, count);
}
if (count == frequencyAndItems.size()) {
LinkedList<Integer> a = new LinkedList<>();
a.add(Integer.MAX_VALUE);
frequencyAndItems.add(a);
}
try{
frequencyAndItems.get(count).add(x);
}catch (IndexOutOfBoundsException iex){
System.out.println(x+" "+ count);
} } public int pop() { int size = frequencyAndItems.size() - 1;
// Get the max frequency
LinkedList<Integer> maxFrequency = frequencyAndItems.get(size);
// find the element to remove
Integer item = maxFrequency.getLast();
// Update the counter
int c = counter.get(item);
c=c-1;
counter.put(item,c); // get the position of the item in the queue
int index = queue.lastIndexOf(item);
//remove from the queue
queue.remove(index);
//remove the item from the frequency and item queue
maxFrequency.removeLast(); if (maxFrequency.size() == 1 & maxFrequency.getLast() == Integer.MAX_VALUE) {
frequencyAndItems.removeLast();
}
return item; }
}