Code Destine

Problem Statement

Design a Maximum Frequency Stack data structure that supports the following operations in constant time O(1).

1. push(N) :- It insert element N onto the top of the stack.
2. pop() :- It removes and returns the most frequent element from the stack. If there are two or more, most frequent elements, then the element closest to the top of the stack is removed and returned.

Example 

FrequencyStack stack = new FrequencyStack();		
stack.push(4);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(4);
stack.push(3);
stack.pop(); -- value: 4
stack.pop(); -- value: 3

Solution

To design the maximum frequency stack data structure, two HashMap objects, and one integer variable will be used. The role of these objects and variable are as follows:

1. HashMap<Integer, Integer> frequencyMap:- It contains the element E pushed into the stack as a key and its frequency F as a value.
2. HashMap<Integer, Stack<Integer>> groupMap:- It contains the frequency F as a key and the stack containing all the element having same frequency F as a value.
3. Integer maxFrequency:- It is the maximum frequency of the elements stored in the stack.

Each operation of the maximum frequency stack will work in the following way:

1. push(N) :- It put’s the element N into the frequencyMap as a key and increased its value (frequency F) by 1 (default value 1 in case of new entry). If frequency F is greater than maxFrequency, then update the maxFrequency value as F. In the end, it check’s the groupMap, if it contains the maxFrequency as key. If yes, then it get the value stack and push the element N on to its top. If not, then it creates an object of the stack and push element N on to its top and put this stack as a value against maxFrequency key into the groupMap.
2. pop() :- It pop’s the element from the top of the stack (stack stored in the groupMap against the maxFrequency key) and decrease the frequency of popped element stored in the frequencyMap by 1. If stack is empty, then it deletes maxFrequency entry from the groupMap and decrease the maxFrequency value by 1.

Program

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class FrequencyStack {
	
	public static void main(String[] args) {		
		FrequencyStack stack = new FrequencyStack();		
		stack.push(4);
		stack.push(2);
		stack.push(3);
		stack.push(4);
		stack.push(4);
		stack.push(3);
		System.out.println("Pop: " + stack.pop());
		System.out.println("Pop: " + stack.pop());							
	} 
	
	Map<Integer,Integer> frequencyMap;
    Map<Integer,Stack<Integer>> groupMap;
    int maxfrequency;

    public FrequencyStack() {
        frequencyMap = new HashMap<>();
        groupMap = new HashMap<>();
        maxfrequency = 0;
    }
    
    public void push(int x) {
        
        frequencyMap.put(x, frequencyMap.getOrDefault(x, 0)+1);
        int freq = frequencyMap.get(x);
        
        if(freq > maxfrequency){
            maxfrequency = freq;
        }
        
        if(groupMap.containsKey(freq)){
            groupMap.get(freq).push(x);
        }else {
            Stack<Integer> stack = new Stack<>();
            stack.push(x);
            groupMap.put(freq, stack);
        }        
    }
    
    public int pop() {
        int x = groupMap.get(maxfrequency).pop();
        frequencyMap.put(x, frequencyMap.getOrDefault(x, 0)-1);
        if(groupMap.get(maxfrequency).size()==0){
            maxfrequency--;
        }
        return x;
    }
}

Result

Pop: 4
Pop: 3

Similar Post

1. Remove All Adjacent Duplicates In String
2. Backspace String Compare
3. Valid Parentheses

That’s all for Design Maximum Frequency Stack Data Structure in Java, If you liked it, please share your thoughts in a comments section and share it with others too.