Dinesh on Java

In this article, we will discuss how to create a Data Structure with Insert, Delete and GetMostFrequent operations of O(1). This Data Structure will proform Insert, delete, and get the most frequent item in the constant time.

As we know that the insertion and deletion will be performed on a hash map with the constant time O(1). So, a hash map will be the right choice for insertion and deletion. But, how to implement get most frequent method with O(1) time.

Let’s see the following implementation of this method to achieve get the most frequent item with O(1) time.

Other Data Structures Articles

1. Create a LRU cache
2. Create a LFU cache

Create a Data Structure with Insert, Delete and GetMostFrequent of O(1)

We will get the solution for this problem by using HashMap and LinkedList. Let’ see the following code:

/**
 * 
 */
package com.dineshonjava.algo.gmf;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Dinesh.Rajput
 *
 */
public class Node {
	
	int value;
	Node prev;
	Node next;
	Set<Integer> set;
 
	public Node(int v){
		value = v;
		set = new HashSet<Integer>();
	}
}

We will use the LinkedList to hold the frequency of the item in the data structure along with the item stored in the HashSet. This set will contain all items with the same frequency. Let’s see the other class of our Data structure.

/**
 * 
 */
package com.dineshonjava.algo.gmf;

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

/**
 * @author Dinesh.Rajput
 *
 */
public class GetMostFrequent {
	
	Map<Integer, Node> map;
	Node tail, head;
	
	/** Initialize your data structure here. */
	public GetMostFrequent() {
		super();
		map = new HashMap<>();
	}
	
	/** Adding items to your data structure. */
	public void add(int val) {
		
		if(map.containsKey(val)) {
			Node node = map.get(val);
			node.set.remove(val);
			if(node.next != null) {
				node.next.set.add(val);
				map.put(val, node.next);
			}else {
				Node newnode = new Node(node.value+1);
				newnode.set.add(val);
				map.put(val, newnode);
				node.next = newnode;
				newnode.prev = node;
				tail = newnode;
			}
		}else {
			if(head != null && tail != null) {
				if(tail.value > 1) {
					head.set.add(val);
					map.put(val, head);
				}else {
					tail.set.add(val);
					map.put(val, tail);
				}
			}else {
				Node node = new Node(1);
				node.set.add(val);
				map.put(val, node);
				head = node;
				tail = node;
			}
		}
	}
	
	/** Getting most frequent item from your data structure. */
	public int getMostFrequent() {
		
		if(tail == null)
			return -1;
		
		return tail.set.iterator().next();
	}
	
	/** Removing item from your data structure. */
	public void remove(int val) {
		
		if(map.containsKey(val)) {
			Node node = map.get(val);
			node.set.remove(val);
			
			if(node.value == 1){
				map.remove(val);
			}else{
				node.prev.set.add(val);
				map.put(val, node.prev);
			}
			
			while(tail != null && tail.set.size() == 0){
				tail = tail.prev;
			}
			
		}else {
			System.out.println("No such item exist!!!");
		}
	}
}

The above GetMostFrequent our collection data structure class, it has three methods add(), remove(), and getMostFrequent(). All these methods have time complexity of O(1).

Let’s create a test class for this data structure as the following:

/**
 * 
 */
package com.dineshonjava.algo.gmf;

/**
 * @author Dinesh.Rajput
 *
 */
public class GMFTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		//Creating your data structure object
		GetMostFrequent frequent = new GetMostFrequent();
		
		//Adding items to your data structure with O(1)
		frequent.add(2);
		frequent.add(3);
		frequent.add(4);
		frequent.add(5);
		frequent.add(2);
		frequent.add(6);
		frequent.add(3);
		frequent.add(3);
		frequent.add(2);
		frequent.add(2);
		
		//Getting most frequent item from your data structure with O(1)
		System.out.println("Most frequent number in the collection is "+frequent.getMostFrequent()); //Expected 2
		
		//Removing item from your data structure with O(1)
		frequent.remove(2);
		frequent.remove(2);
		
		System.out.println("Most frequent number in the collection is "+frequent.getMostFrequent()); //Expected 3
		
	}

}

Let’s run this test class and see the following output.

Most frequent number in the collection is 2
Most frequent number in the collection is 3