top of page
Search

Maximum Frequency Stack

Updated: Mar 24, 2021

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:


class FreqStack {

    PriorityQueue<int[]> queue;
    Map<Integer,Integer> map;
    int i=0;
    public FreqStack() {
        map=new HashMap<>();
        queue = new PriorityQueue<>((a,b)->a[1]==b[1]?b[2]-a[2]:b[1]-a[1]);
    }
    
    public void push(int x) {
        map.put(x,map.getOrDefault(x,0)+1);
        int[] a = {x,map.get(x),i++};
        queue.add(a);
    }
    
    public int pop() {
        int[] a=queue.poll();
        map.put(a[0],map.getOrDefault(a[0],0)-1);
        return a==null?-1:a[0];        
    }
}

19 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

bottom of page