Find the "Kth" Max and Min Element of an Array

Understanding the Problem

The goal is to find the Kth maximum and Kth minimum element in an array using different methods.

Method 1: Sorting Approach

This method sorts the array and directly retrieves the Kth min and max elements.

import java.util.Arrays;

public class KthElement {
    public static void findKthMinMax(int[] arr, int k) {
        Arrays.sort(arr);
        System.out.println(k + "th Minimum Element: " + arr[k - 1]);
        System.out.println(k + "th Maximum Element: " + arr[arr.length - k]);
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        findKthMinMax(arr, k);
    }
}
            

Output:

3rd Minimum Element: 7
3rd Maximum Element: 10

Method 2: Using PriorityQueue (Heap)

This method uses a min-heap to find the Kth largest and smallest element.

import java.util.PriorityQueue;

public class KthElementHeap {
    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(k + "th Largest Element: " + kthLargest(arr, k));
    }
}
            

Output:

3rd Largest Element: 10

Method 3: QuickSelect Algorithm

This method optimizes finding the Kth smallest element using partitioning.

import java.util.Random;

public class KthElementQuickSelect {
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, high);
        return i;
    }

    private static int quickSelect(int[] arr, int low, int high, int k) {
        if (low <= high) {
            int pi = partition(arr, low, high);
            if (pi == k - 1) return arr[pi];
            else if (pi > k - 1) return quickSelect(arr, low, pi - 1, k);
            else return quickSelect(arr, pi + 1, high, k);
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 3;
        System.out.println(k + "th Smallest Element: " + quickSelect(arr, 0, arr.length - 1, k));
    }
}
            

Output:

3rd Smallest Element: 7