WAP to Find Kth Largest Element in an Array

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

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

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