WAP to Find Kth Smallest Element in an Array

Kth Smallest Element in an Array: This Java program finds the Kth smallest element in an array of integers. It efficiently finds the Kth smallest element using the built-in sorting functionality provided by the Arrays.sort method.

Find Kth Smallest Element in an Array

package com.softwaretestingo.interviewprograms;
import java.util.Arrays;
public class InterviewPrograms83 
{
	// Function to return K'th smallest
	// element in a given array
	public static int kthSmallest(Integer[] arr, int K)
	{
		// Sort the given array
		Arrays.sort(arr);

		// Return K'th element in
		// the sorted array
		return arr[K - 1];
	}

	public static void main(String[] args) 
	{
		Integer arr[] = new Integer[] { 12, 3, 5, 7, 19 };
		int K = 2;

		// Function call
		System.out.print("K'th smallest element is "+ kthSmallest(arr, K));
	}

}

Output

K'th smallest element is 5

Alternative Way 1:

This Java program finds the K-th smallest element from an array of integers without using sorting. It achieves this by using a TreeSet, which automatically maintains the elements in sorted order. The program iterates through the TreeSet to find the K-th smallest element.

package com.softwaretestingo.interviewprograms;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
public class InterviewPrograms83_1 
{
	public static void main(String[] args) 
	{
		int[] arr = { 12, 3, 5, 7, 19 };
		int N = arr.length;
		int K = 2;
		int position=K;

		// since counting starts from 0 so to find kth
		// element we need to reduce K by 1
		K--;

		// for storing elements in sorted form
		// in set we will use TreeSet
		Set<Integer> s = new TreeSet<Integer>();

		// Adding elements to set
		for (int i = 0; i < N; i++)
			s.add(arr[i]);

		// Use iterator method of Iterator
		// for the traversal
		Iterator<Integer> itr = s.iterator();

		while (K > 0)
		{
			itr.next();
			K--;
		} // itr points to the Kth element in the set

		System.out.println("The "+position+" Smallest Element is "+itr.next());
	}

}

Output

The 2 Smallest Element is 5

Alternative Way 2:

This Java program finds the kth smallest element from an array of integers using the Bubble Sort algorithm. It takes input from the user, sorts the array in ascending order using Bubble Sort, and then identifies the kth smallest element.

package com.softwaretestingo.interviewprograms;
import java.util.Scanner;
public class InterviewPrograms83_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 ;
				}
			}
		}
		// pointing to the kth smallest element
		for (i=0; i<k; i++);
		System.out.print ( "\nThe " + k + " th smallest element is : " + a[i-1]);
	}
	public static void main(String[] args) 
	{
		// creating an object
		InterviewPrograms83_2 k = new InterviewPrograms83_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 : 2

The 2 th smallest element is : 20

Alternative Way 3:

This Java program finds the kth smallest element from an array of integers using a Priority Queue (max-heap) to keep track of the k-smallest elements efficiently. The program takes input from the user, where the user can specify the value of k, and then it finds and prints the kth smallest element from the array.

package com.softwaretestingo.interviewprograms;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
public class InterviewPrograms83_3 
{
	public static int  kthSmallestElement(int  k, int[] array)
	{
		PriorityQueue<Integer> maxHeap = new  PriorityQueue<>(Collections.reverseOrder());
		int  length = array.length;
		for  (int  i = 0; i < length; i++)
		{
			maxHeap.add(array[i]);
			if  (maxHeap.size() > k)
			{
				maxHeap.poll();
			}
		}
		return  maxHeap.peek();
	}

	public static void main(String[] args) 
	{
		int [] array = {1, 3, 8, 9, 4, 7, 6};
		
		Scanner sc = new Scanner(System.in);
		System.out.print("Enter the value of k : ");
		int k = sc.nextInt();
		
		
		System.out .println("The "+k+" Smallest Element is "+kthSmallestElement(k, array));
	}

}

Output

Enter the value of k : 3
The 3 Smallest Element is 4