Kth Largest Element in an Array: This Java program finds the k-th largest element from an array of integers using a min-heap. Let’s break down the program step by step to understand what it does:
Find Kth Largest Element in an Array
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class InterviewPrograms82
{
// Function to find the k'th largest element in an array using min-heap
public static int findKthLargest(List<Integer> ints, int k)
{
// base case
if (ints == null || ints.size() < k) {
System.exit(-1);
}
// create a min-heap using the `PriorityQueue` class and insert
// the first `k` array elements into the heap
PriorityQueue<Integer> pq = new PriorityQueue<>(ints.subList(0, k));
// do for remaining array elements
for (int i = k; i < ints.size(); i++)
{
// if the current element is more than the root of the heap
if (ints.get(i) > pq.peek())
{
// replace root with the current element
pq.poll();
pq.add(ints.get(i));
}
}
// return the root of min-heap
return pq.peek();
}
public static void main(String[] args)
{
List<Integer> ints = Arrays.asList(17, 24, 6, 3, 39, 1);
Scanner sc = new Scanner(System.in);
System.out.print("Enter the value of k : ");
int k = sc.nextInt();
System.out.println(k+" largest array element From Array is " + findKthLargest(ints, k));
}
}
Output
Enter the value of k : 3 3 largest array element From Array is 17
Explanation:
- First, the program defines a class named InterviewPrograms82. This class contains two methods: findKthLargest and main.
- The findKthLargest method takes a list of integers (List<Integer> ints) and an integer k as parameters and returns the k-th largest element from the list.
- Inside the findKthLargest method, there is a base case check to handle scenarios where the input list is null or its size is less than k. In such cases, the program exits with an error code (System.exit(-1)).
- A PriorityQueue<Integer> named pq is created. A PriorityQueue is a min-heap in Java by default, meaning the smallest element is always at the root. The first k elements from the input list are added to this priority queue during its initialization. As a result, pq contains the k-smallest elements from the list.
- Next, a loop runs from index k to the end of the list. This loop iterates through the remaining elements of the list after the k-smallest elements.
- For each element in the loop, it is compared with the root of the min-heap (pq.peek()). If the current element is larger than the root of the heap, it means it should be one of the k-largest elements in the list.
- In this case, the root element is removed from the heap using pq.poll() (as it is the smallest element), and the current element is added to the heap using pq.add(ints.get(i)).
- After the loop ends, the min-heap (pq) will contain the k-largest elements from the input list, and its root element will be the k-th largest element.
- The findKthLargest method returns the root of the min-heap, which is the k-th largest element.
- In the main method, an array of integers ints is created and initialized with the values {17, 24, 6, 3, 39, 1}.
- The program asks the user to input the value of k (which indicates the k-th largest element to find) using the Scanner class.
- Finally, the program calls the findKthLargest method with the input list and k, and it prints the result – the k-th largest element from the input list. For example, if k is 2, it will print the second-largest element from the list.
Alternative Way 1
This Java program finds the k-th largest element from an array of integers using a max-heap. It uses a priority queue to efficiently find the k-th largest element without sorting the entire array. Let’s break down the program step by step to understand what it does:
package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class InterviewPrograms82_1
{
// Function to find the k'th largest element in an array using max-heap
public static int findKthLargest(List<Integer> ints, int k)
{
// base case
if (ints == null || ints.size() < k)
{
System.exit(-1);
}
// build a max-heap using the `PriorityQueue` class from all
// elements in the list
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
// or pass `Comparator.reverseOrder()`
pq.addAll(ints);
// pop from max-heap exactly `k-1` times
while (--k > 0)
{
pq.poll();
}
// return the root of max-heap
return pq.peek();
}
public static void main(String[] args)
{
List<Integer> ints = Arrays.asList(7, 4, 6, 3, 9, 1);
int k = 2;
System.out.println("k'th largest array element is " + findKthLargest(ints, k));
}
}
Output
k'th largest array element is 7
StepBy Step Explanation:
- First, the program defines a class named InterviewPrograms82_1. This class contains two methods: findKthLargest and main.
- The findKthLargest method takes a list of integers (List<Integer> ints) and an integer k as parameters and returns the k-th largest element from the list.
- Inside the findKthLargest method, there is a base case check to handle scenarios where the input list is null or its size is less than k. In such cases, the program exits with an error code (System.exit(-1)).
- A PriorityQueue<Integer> named pq is created. This priority queue is initialized with a custom comparator (a, b) -> b – a, which means it will behave as a max-heap. A max-heap ensures that the largest element is always at the root.
- All elements from the input list (ints) are added to this max-heap using pq.addAll(ints). The max-heap will automatically reorder the elements, so the largest element will be at the root.
- The program then proceeds to find the k-th largest element. To do this, it performs a pop operation (pq.poll()) from the max-heap exactly k-1 times. This removes the k-1 largest elements, leaving the k-th largest element at the root of the max-heap.
- After the loop ends, the root of the max-heap (pq.peek()) will contain the k-th largest element from the input list.
- The findKthLargest method returns the root of the max-heap, which is the k-th largest element.
- In the main method, an array of integers ints is created and initialized with the values {7, 4, 6, 3, 9, 1}.
- The program sets the value of k to 2, indicating that it needs to find the second-largest element from the list.
- Finally, the program calls the findKthLargest method with the input list and k, and it prints the result – the k-th largest element from the input list. In this case, it will print “k’th largest array element is 7” since the second-largest element in the list is 7.
Alternative Way 2:
This Java program finds the k-th largest element from an array of integers using a simple sorting technique. It takes input from the user, sorts the array in ascending order, and then identifies the k-th largest element. Let’s break down the program step by step to understand what it does:
package com.softwaretestingo.interviewprograms;
import java.util.Scanner;
public class InterviewPrograms82_2
{
int a[] = new int[20], n, k;
// function to take input
void accept ( )
{
int i ;
// taking the inputs
Scanner sc = new Scanner(System.in);
System.out.print(" Enter the number of elements : ");
n = sc.nextInt();
System.out.print ("Enter the array elements : ");
for (i=0; i<n; i++ )
{
a[i] = sc.nextInt();
}
System.out.print("Enter the value of k : ");
k = sc.nextInt();
}
//function to find the kth largest or smallest
void find ( )
{
int i, j, t;
// sorting the list / array in ascending order
for (i=0; i<n; i++ )
{
for (j=0; j<n-i-1; j++)
{
if (a[j]>a[j+1])
{
t = a[j];
a[j]= a[j+1];
a[j+1] = t ;
}
}
}
// printing the sorted array
System.out.print("The sorted list is : ");
for (i=0; i<n; i++ )
{
System.out.print (a[i]+" ");
}
// finding the kth largest element
if ( 1 == 1 )
{
// pointing to the kth largest element
for (i=n-1; i>=n-k; i--) ;
System.out.print ("\nThe " + k + " th largest element is : " + a [ i + 1 ] ) ;
}
}
public static void main(String[] args)
{
// creating an object
InterviewPrograms82_2 k = new InterviewPrograms82_2();
// calling the functions
k.accept();
k.find();
}
}
Output
Enter the number of elements : 5 Enter the array elements : 10 20 30 40 50 Enter the value of k : 3 The sorted list is : 10 20 30 40 50 The 3 th largest element is : 30
Step By Step Explanation
- The program defines a class named InterviewPrograms82_2. Inside this class, there are three instance variables: a (an integer array to store elements), n (an integer to store the number of elements in the array), and k (an integer to store the value of k for finding the k-th largest element).
- The class contains three methods: accept, find, and main.
- The accept method is used to take input from the user. It creates a Scanner object to read inputs from the console. It asks the user to enter the number of elements (n) and the array elements (a), and also the value of k.
- The find method is used to find the k-th largest element from the array. It first sorts the array in ascending order using the Bubble Sort algorithm, which compares adjacent elements and swaps them if they are in the wrong order. Bubble Sort is not an efficient sorting algorithm but is used here for simplicity.
- After sorting the array, the program prints the sorted list.
- The method then uses an if statement with an always true condition if ( 1 == 1 ) (which is likely unintentional, and can be removed) to find the k-th largest element. Inside the block, it starts from the end of the sorted array and goes backwards to identify the k-th largest element.
- Finally, the program prints the k-th largest element.
- In the main method, an object of the InterviewPrograms82_2 class is created, and its methods accept and find are called to perform the required operations.
It’s important to note that the approach taken in this program (using Bubble Sort and finding the k-th largest element) is not the most efficient way to achieve this task. More efficient algorithms and data structures, like the ones shown in the previous examples, can find the k-th largest element in better time complexity.
