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 <stdio.h>
#include <stdlib.h>

void findKthMinMax(int arr[], int n, int k) {
    qsort(arr, n, sizeof(int), (int (*)(const void *, const void *)) compare);
    printf("%dth Minimum Element: %d\n", k, arr[k - 1]);
    printf("%dth Maximum Element: %d\n", k, arr[n - k]);
}

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

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 <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i, left = 2*i + 1, right = 2*i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    for (int i = n/2 - 1; i >= 0; i--) heapify(arr, n, i);
}

int kthLargest(int arr[], int n, int k) {
    buildHeap(arr, n);
    for (int i = 0; i < k - 1; i++) {
        arr[0] = arr[n-1];
        n--;
        heapify(arr, n, 0);
    }
    return arr[0];
}

int main() {
    int arr[] = {7, 10, 4, 3, 20, 15};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    printf("%dth Largest Element: %d\n", k, kthLargest(arr, n, k));
    return 0;
}
            

Output:

3rd Largest Element: 10

Method 3: QuickSelect Algorithm

This method optimizes finding the Kth smallest element using partitioning.

#include <stdio.h>

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) {
            int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
            i++;
        }
    }
    int temp = arr[i]; arr[i] = arr[high]; arr[high] = temp;
    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;
    printf("%dth Smallest Element: %d\n", k, quickSelect(arr, 0, n - 1, k));
    return 0;
}
            

Output:

3rd Smallest Element: 7