WikiGalaxy
Kth Smallest and Largest Elements
Introduction
In many computational problems, finding the Kth smallest or largest element in a data set is crucial. This can be applied in statistics, data analysis, and competitive programming.
Example 1: Using Sorting
Approach
The simplest way to find the Kth smallest or largest element is to sort the array and pick the Kth element.
import java.util.Arrays;
class KthElement {
public static int kthSmallest(int[] arr, int k) {
Arrays.sort(arr);
return arr[k - 1];
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int k = 3;
System.out.println("Kth smallest element is " + kthSmallest(arr, k));
}
}
Console Output:
Kth smallest element is 7
Example 2: Using Min-Heap
Approach
A more efficient approach for large datasets is to use a Min-Heap to find the Kth largest element.
import java.util.PriorityQueue;
class KthElement {
public static int kthLargest(int[] arr, int k) {
PriorityQueue minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int k = 3;
System.out.println("Kth largest element is " + kthLargest(arr, k));
}
}
Console Output:
Kth largest element is 10
Example 3: Using Quickselect
Approach
Quickselect is an efficient algorithm based on the QuickSort partitioning technique to find the Kth smallest element.
class KthElement {
public static int quickSelect(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, k - 1);
}
private static int quickSelect(int[] nums, int low, int high, int k) {
if (low == high) return nums[low];
int pivotIndex = partition(nums, low, high);
if (k == pivotIndex) {
return nums[k];
} else if (k < pivotIndex) {
return quickSelect(nums, low, pivotIndex - 1, k);
} else {
return quickSelect(nums, pivotIndex + 1, high, k);
}
}
private static int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] <= pivot) {
swap(nums, i, j);
i++;
}
}
swap(nums, i, high);
return i;
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void main(String[] args) {
int[] arr = {3, 2, 1, 5, 6, 4};
int k = 2;
System.out.println("Kth smallest element is " + quickSelect(arr, k));
}
}
Console Output:
Kth smallest element is 2
Example 4: Using Max-Heap
Approach
To find the Kth smallest element, a Max-Heap can be used. This is efficient when K is small compared to the size of the array.
import java.util.Collections;
import java.util.PriorityQueue;
class KthElement {
public static int kthSmallest(int[] arr, int k) {
PriorityQueue maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int num : arr) {
maxHeap.add(num);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
return maxHeap.peek();
}
public static void main(String[] args) {
int[] arr = {12, 3, 5, 7, 19};
int k = 4;
System.out.println("Kth smallest element is " + kthSmallest(arr, k));
}
}
Console Output:
Kth smallest element is 12
Example 5: Using TreeSet
Approach
Using a TreeSet, we can maintain a sorted order of elements dynamically, which can be used to find the Kth smallest or largest element.
import java.util.TreeSet;
class KthElement {
public static int kthSmallest(int[] arr, int k) {
TreeSet treeSet = new TreeSet<>();
for (int num : arr) {
treeSet.add(num);
}
int count = 0;
for (int num : treeSet) {
if (++count == k) return num;
}
return -1; // Should never reach here if k is valid
}
public static void main(String[] args) {
int[] arr = {8, 16, 4, 12, 10};
int k = 3;
System.out.println("Kth smallest element is " + kthSmallest(arr, k));
}
}
Console Output:
Kth smallest element is 10
