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.

#include <iostream>
#include <algorithm>

using namespace std;

void findKthMinMax(int arr[], int n, int k) {
    sort(arr, arr + n);
    cout << k << "th Minimum Element: " << arr[k - 1] << endl;
    cout << k << "th Maximum Element: " << arr[n - k] << endl;
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    int n = sizeof(arr) / sizeof(arr[0]), k = 3;
    findKthMinMax(arr, n, k);
    return 0;
}
            

Output:

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

Method 2: Using Heap

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

#include <iostream>
#include <queue>
using namespace std;

int kthLargest(int arr[], int n, int k) {
    priority_queue maxHeap(arr, arr + n);
    for (int i = 0; i < k - 1; i++) maxHeap.pop();
    return maxHeap.top();
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    int n = sizeof(arr) / sizeof(arr[0]), k = 3;
    cout << k << "th Largest Element: " << kthLargest(arr, n, k) << endl;
    return 0;
}
            

Output:

3rd Largest Element: 10

Method 3: QuickSelect Algorithm

This method optimizes finding the Kth smallest element using partitioning.

#include <iostream>
using namespace std;

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

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;
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    int n = sizeof(arr) / sizeof(arr[0]), k = 3;
    cout << k << "th Smallest Element: " << quickSelect(arr, 0, n - 1, k) << endl;
    return 0;
}
            

Output:

3rd Smallest Element: 7