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.

def find_kth_min_max(arr, k):
    arr.sort()
    print(f"{k}th Minimum Element: {arr[k-1]}")
    print(f"{k}th Maximum Element: {arr[-k]}")

arr = [7, 10, 4, 3, 20, 15]
k = 3
find_kth_min_max(arr, k)
            

Output:

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

Method 2: Using Heap

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

import heapq

def kth_largest(arr, k):
    return heapq.nlargest(k, arr)[-1]

def kth_smallest(arr, k):
    return heapq.nsmallest(k, arr)[-1]

arr = [7, 10, 4, 3, 20, 15]
k = 3
print(f"{k}th Largest Element: {kth_largest(arr, k)}")
print(f"{k}th Smallest Element: {kth_smallest(arr, k)}")
            

Output:

3rd Largest Element: 10
3rd Smallest Element: 7

Method 3: QuickSelect Algorithm

This method optimizes finding the Kth smallest element using partitioning.

import random

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

def quickselect(arr, low, high, k):
    if low <= high:
        pi = partition(arr, low, high)
        if pi == k - 1:
            return arr[pi]
        elif pi > k - 1:
            return quickselect(arr, low, pi - 1, k)
        else:
            return quickselect(arr, pi + 1, high, k)
    return -1

arr = [7, 10, 4, 3, 20, 15]
k = 3
print(f"{k}th Smallest Element: {quickselect(arr, 0, len(arr) - 1, k)}")
            

Output:

3rd Smallest Element: 7