Kth Smallest Element in an Array: This Java program finds the K-th smallest element from an array of integers. It uses the built-in sorting functionality provided by the Arrays.sort method to efficiently find the K-th smallest element.
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
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms83.
- Inside the class, there is a single static method named kthSmallest that takes two parameters: an array of Integers (Integer[] arr) and an integer K which represents the K-th smallest element to find.
- The kthSmallest method is designed to find the K-th smallest element in the array. To do this, it first sorts the given array arr in ascending order using the Arrays.sort method. Sorting the array is a crucial step to determine the K-th smallest element.
- After sorting the array, the method returns the K-th element of the sorted array by accessing arr[K – 1]. Since arrays are zero-indexed in Java, the K-th smallest element is at index K – 1.
- In the main method, an array of Integers arr is created and initialized with the values {12, 3, 5, 7, 19}.
- The program sets the value of K to 2, indicating that it needs to find the second smallest element from the array.
- Finally, the program calls the kthSmallest method with the input array and K, and it prints the result – the K-th smallest element from the array. In this case, it will print “K’th smallest element is 5” since the second smallest element in the array is 5.
In summary, the program uses sorting to find the K-th smallest element, making use of Java’s built-in Arrays.sort method to achieve this efficiently.
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
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms83_1.
- Inside the main method, an array of integers arr is created and initialized with the values {12, 3, 5, 7, 19}.
- The program sets the value of N to the length of the array arr, which represents the total number of elements in the array.
- The program sets the value of K to 2, indicating that it needs to find the second smallest element from the array.
- The program sets the value of position to K, which will be used later to display the position of the K-th smallest element in the output.
- Since the counting of elements in the array starts from 0 in Java, the program decreases the value of K by 1 (K–). This adjustment allows us to find the correct index in the set to get the K-th smallest element.
- A TreeSet<Integer> named s is created. A TreeSet is used because it automatically sorts the elements in ascending order.
- The program then adds all the elements from the arr array to the s TreeSet using a loop. As elements are added to the TreeSet, they are sorted in ascending order.
- The program creates an iterator named itr to traverse through the TreeSet.
- A loop runs K times, and in each iteration, the program calls itr.next(), which moves the iterator to the next element in the sorted set. This loop brings the iterator to the K-th smallest element in the set.
- After the loop, the iterator points to the K-th smallest element in the set.
- The program then prints the K-th smallest element along with its position in the original array by calling itr.next() again. Since we already moved the iterator K times in the previous loop, calling itr.next() now will retrieve the K-th smallest element from the set.
- The output will be something like “The 2 Smallest Element is 5”, indicating that the second smallest element in the original array is 5.
In summary, the program finds the K-th smallest element from the array using a TreeSet, which automatically sorts the elements. This method avoids sorting the entire array and provides a more efficient way to find the K-th smallest element.
Alternative Way 2:
This Java program finds the k-th 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 k-th 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
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms83_2.
- Inside the 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 smallest element).
- The class contains two methods: accept and find.
- 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), the array elements (a), and also the value of k.
- The find method is used to find the k-th smallest element from the array. It first sorts the given array a in ascending order using the Bubble Sort algorithm. Bubble Sort compares adjacent elements and swaps them if they are in the wrong order. It is a simple sorting algorithm but not the most efficient one.
- After sorting the array, the program points to the k-th smallest element in the array by iterating i from 0 to k – 1.
- The program then prints the k-th smallest element.
- In the main method, an object of the InterviewPrograms83_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 smallest 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 smallest element in better time complexity. Nonetheless, this program demonstrates the basic concept of finding the k-th smallest element using a simple sorting algorithm.
Alternative Way 3:
This Java program finds the k-th smallest element from an array of integers using a Priority Queue (max-heap) to efficiently keep track of the k smallest elements. The program takes input from the user, where the user can specify the value of k, and then it finds and prints the k-th 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
Let’s break down the program step by step to understand what it does:
- The program defines a class named InterviewPrograms83_3.
- Inside the class, there is a single static method named kthSmallestElement that takes two parameters: an integer k representing the k-th smallest element to find, and an array of integers array.
- Inside the kthSmallestElement method, a PriorityQueue<Integer> named maxHeap is created. A PriorityQueue in Java is a min-heap by default, but in this program, it is used as a max-heap by providing Collections.reverseOrder() as a parameter to the constructor. A max-heap ensures that the largest element is always at the root.
- The length variable is used to store the size of the input array.
- The method then iterates through each element of the input array using a loop. For each element, it adds the element to the maxHeap and checks if the size of the maxHeap is greater than k. If the size exceeds k, it removes the largest element (root) from the maxHeap using maxHeap.poll(). This step ensures that the maxHeap only contains the k smallest elements at any point.
- After iterating through the entire array, the root of the maxHeap contains the k-th smallest element.
- The method returns the k-th smallest element, which is obtained using maxHeap.peek().
- In the main method, an array of integers array is created and initialized with the values {1, 3, 8, 9, 4, 7, 6}.
- The program asks the user to input the value of k (which indicates the k-th smallest element to find) using the Scanner class.
- Finally, the program calls the kthSmallestElement method with the input array and k, and it prints the result – the k-th smallest element from the input array. For example, if k is 2, it will print the second smallest element from the array.
In summary, the program efficiently finds the k-th smallest element from an array using a Priority Queue (max-heap) to keep track of the k smallest elements without the need for sorting the entire array.
