To find the Kth smallest or largest element in an unsorted array in Java

Category : Java | Sub Category : Java Programs | By Prasad Bonam Last updated: 2023-08-14 12:38:17 Viewed : 563

To find the Kth smallest or largest element in an unsorted array in Java, you can use sorting, priority queues (heap), or quickselect algorithms. Here is how you can implement each of these approaches:

1. Using Sorting: One simple approach is to sort the array in ascending order and then directly access the K-1 indexed element for Kth smallest or the (n-K) indexed element for Kth largest.

javaCopy code
import java.util.Arrays;

public class KthSmallestLargest {
    public static void main(String[] args) {
        int[] array = {12, 3, 5, 7, 19};
        int k = 3; // Find the 3rd smallest element
        
        Arrays.sort(array);
        
        System.out.println("Kth smallest element: " + array[k - 1]);
    }
}

2. Using Priority Queue (Heap): You can use a MinHeap for finding the Kth smallest element and a MaxHeap for finding the Kth largest element. Here is an example using a MinHeap for Kth smallest:

javaCopy code
import java.util.PriorityQueue;

public class KthSmallestLargest {
    public static void main(String[] args) {
        int[] array = {12, 3, 5, 7, 19};
        int k = 3; // Find the 3rd smallest element
        
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int num : array) {
            minHeap.offer(num);
        }
        
        for (int i = 1; i < k; i++) {
            minHeap.poll();
        }
        
        System.out.println("Kth smallest element: " + minHeap.peek());
    }
}

3. Using Quickselect Algorithm: The Quickselect algorithm is a variation of the QuickSort algorithm that finds the Kth smallest or largest element in linear time on average.

javaCopy code
public class KthSmallestLargest {
    public static void main(String[] args) {
        int[] array = {12, 3, 5, 7, 19};
        int k = 3; // Find the 3rd smallest element
        
        int result = quickSelect(array, 0, array.length - 1, k - 1);
        
        System.out.println("Kth smallest element: " + result);
    }
    
    public static int quickSelect(int[] arr, int left, int right, int k) {
        int pivotIndex = partition(arr, left, right);
        
        if (pivotIndex == k) {
            return arr[pivotIndex];
        } else if (pivotIndex < k) {
            return quickSelect(arr, pivotIndex + 1, right, k);
        } else {
            return quickSelect(arr, left, pivotIndex - 1, k);
        }
    }
    
    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        
        for (int j = left; j < right; j++) {
            if (arr[j] <= pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;
        
        return i;
    }
}

In all of these approaches, replace k with the desired K value to find the Kth smallest or largest element.