CC-3 : Find Kth largest number in an Array.

Description:

Given an array of integers as input array, find the kth largest number within the same.

Test cases and expected outputs:

Input Parameters	Expected outputs
int[] nums= {3,4,7,9,10,15, 17, 21}; retVal=hp.findKthLargest(nums, 3);	3rd largest num: 15
int[] nums= {3,4,7,9,10,15, 17, 21}; retVal=hp.findKthLargest(nums, 6);	6th largest num: 7

Pseudocode:

We get array of integers nums as input parameter. We need to find kth largest num and value of k is also received as input parameter.

Initialize a PriorityQueue instance to be used as min Heap.

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

Add nums[idx]to PriorityQueue.

If PriorityQueue size is > k, remove the top element from PriorityQueue.

Return top element of PriorityQueue, it is the k th largest element of the input array.

Code:

public int findKthLargest(int[] nums, int k) {
	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
	for (int idx=0; idx < nums.length; idx++) {
		minHeap.add(nums[idx]);
		if (minHeap.size() > k) {
			minHeap.remove();
		}
	}
	return minHeap.element();
}

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.PriorityQueue;

public class HeapFindKthLargestNum {

public int findKthLargest(int[] nums, int k) {
	PriorityQueue<Integer> minHeap=new PriorityQueue<Integer>();
	for (int idx=0; idx < nums.length; idx++) {
		minHeap.add(nums[idx]);
		if (minHeap.size() > k) {
			minHeap.remove();
		}
	}
	return minHeap.element();
}

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 main(String[] args) {
	/***********************
	 Test cases given below
	 *********************/
	int retVal;
	try {
	HeapFindKthLargestNum hp=new HeapFindKthLargestNum();
	int[] nums= {3,4,7,9,10,15, 17, 21};
	printArraySummary(nums, "Nums");
	retVal=hp.findKthLargest(nums, 3);
	System.out.println("3rd largest num: "+ retVal);
	
	retVal=hp.findKthLargest(nums, 6);
	System.out.println("6rd largest num: "+ retVal);
		
	}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	exception.printStackTrace();
	}
		
}
}