CC-7 : Find top K most frequent integers.

Description:

Given a list of integers as an input, find the top K most frequent integers.

Test cases and expected outputs:

Input Parameters	Expected outputs
Input Nums : 3,3,3,4,7,9,3,4,10,15,4,4,4,17,15,21,16,16,16,16,16,16,16	Top 3 most frequent: 3 <- 4 <- 16

Pseudocode:

We get array of integers nums as input parameter. We need to find top k most frequently occurring integers and value of k is also received as input parameter.

Initialize a HashMap named freq which we will use to count the frequency of occurrence of nums in the input array.

Initialize a PriorityQueue instance named minHeap to be used as Min Heap. Provide a comparator to the constructor the PriorityQueue to sort by frequency of occurrence of integer.

Iterate though nums from index 0 to index nums.length-1:

Check if freq already contains nums[idx]. If already present, extract the frequency of the nums[idx] from freq. Increment the frequency by 1 and put nums[idx] and the updated frequency back to the hashMap.

Iterate through keys of hashMap freq:

Add the current key (integer) to minHeap. The comparator provided to minHeap, automatically extracts the frequency corresponding to current key from freq and adds integer to minheap as per required minheap frequency sorting order.

If minHeap’s size is > k, then remove top element from minHeap.

Return minHeap, as it contains the top k frequent integers.

Code:

public PriorityQueue<Integer> findTopKFrequent(int[] nums, int k) {
	HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>((a,b)->freq.get(a)-freq.get(b));
	for (int idx=0; idx < nums.length; idx++) {
		int currFreq=freq.getOrDefault(nums[idx],0);
		freq.put(nums[idx], currFreq+1);
	}	
	Iterator<Integer> itr=freq.keySet().iterator();
	while(itr.hasNext()) {
		minHeap.add(itr.next());
		if (minHeap.size() > k) {
			minHeap.remove();
		}
	}
	return minHeap;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.HashMap;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class HeapFindTopKFrequent {
 
public PriorityQueue<Integer> findTopKFrequent(int[] nums, int k) {
	HashMap<Integer,Integer> freq=new HashMap<Integer,Integer>();
	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>((a,b)->freq.get(a)-freq.get(b));
	for (int idx=0; idx < nums.length; idx++) {
		int currFreq=freq.getOrDefault(nums[idx],0);
		freq.put(nums[idx], currFreq+1);
	}	
	Iterator<Integer> itr=freq.keySet().iterator();
	while(itr.hasNext()) {
		minHeap.add(itr.next());
		if (minHeap.size() > k) {
			minHeap.remove();
		}
	}
	return minHeap;
}

public static void printArraySummary(int[] intArray, String label) throws Exception {
   	// Case 1: The input Array is null !!
	if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
	// Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("************************************************************************");
	System.out.print(label+" : ");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < intArray.length; arrayIndex++) {
			System.out.print(intArray[arrayIndex]);
			if (arrayIndex < intArray.length-1) {System.out.print(",");}
	} 
	System.out.println();
	System.out.println(" ************************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}

public static void printQueue(Queue<Integer> queue, String label) throws Exception   {
    if (queue.size() == 0) { System.out.println("Queue empty"); return; }
    System.out.println();
	System.out.println("******************************************************************");
	System.out.print(label +": ");
	Iterator itr=queue.iterator();
	while (itr.hasNext())  {
	    System.out.print(itr.next());
	    System.out.print(" <- ");
	} 
	System.out.println();
	System.out.println("******************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}

public static void main(String[] args) {
	/**********************
	 Test cases given below:
	 **********************/
	PriorityQueue<Integer> retVal;
	try {
	HeapFindTopKFrequent hp=new HeapFindTopKFrequent();
	int[] nums= {3,3,3,4,7,9,3,4,10,15, 4,4,4, 17,15, 21,16,16,16,16,16,16,16};
	printArraySummary(nums, "Nums");
	retVal=hp.findTopKFrequent(nums, 3);
	printQueue(retVal, "Top 3 most frequent");	
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}