CC-8 : Find Kth largest number in a matrix.

Description:

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

Test cases and expected outputs:

Input Parameters	Expected outputs
The input matrix : 11,32,93, 4,56,90, 5,51,94,	3rd largest element in Matrix: 90

Pseudocode:

We get matrix 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 max Heap. Provide Collections.reverseOrder() as argument to constructor of PriorityQueue, so that it acts as a max Heap.

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

Add nums[rowIdx][colIdx]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 matrix.

Code:

public int findKthLargestInMatrix(int[][] nums, int k) {
	
	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());
	for (int iIdx=0; iIdx < nums.length; iIdx++) {
		for (int jIdx=0; jIdx < nums.length; jIdx++) {
			maxHeap.add(nums[iIdx][jIdx]);
		}
		if (maxHeap.size() > k) {
			maxHeap.remove();
		}
		
	}
	return (int) maxHeap.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.Collections;
import java.util.PriorityQueue;

public class HeapFindKthLargestInMatrix {
 
public int findKthLargestInMatrix(int[][] nums, int k) {
	
	PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(Collections.reverseOrder());
	for (int iIdx=0; iIdx < nums.length; iIdx++) {
		for (int jIdx=0; jIdx < nums.length; jIdx++) {
			maxHeap.add(nums[iIdx][jIdx]);
		}
		if (maxHeap.size() > k) {
			maxHeap.remove();
		}
		
	}
	return (int) maxHeap.element();
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d 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+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	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 {
	HeapFindKthLargestInMatrix hp=new HeapFindKthLargestInMatrix();
	int[][] nums= {{11,32,93}, {4, 56, 90}, {5, 51, 94}};
	print2dArray(nums, "The Arrays");
	retVal=hp.findKthLargestInMatrix(nums, 3);
	System.out.print("3rd largest element in Matrix: "+ retVal);	
		
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}