Python - Find the Kth Maximum and Minimum Elements in an Array

Python – Find the Kth Maximum and Minimum Elements in an Array

Finding the kth maximum and minimum elements in an array is a common problem in data structures and algorithms (DSA) interviews.

This tutorial will walk you through the problem statement, sample inputs and outputs, solution approaches, and Python programs to solve this problem.

Problem Statement

Given an unsorted array arr and an integer k, find the kth smallest (minimum) and kth largest (maximum) elements in the array.

Sample Input and Output

Example 1:

</>

Copy

Input:  arr = [7, 10, 4, 3, 20, 15], k = 3
Output: kth Minimum = 7, kth Maximum = 10

Example 2:

</>

Copy

Input:  arr = [1, 2, 3, 4, 5, 6], k = 2
Output: kth Minimum = 2, kth Maximum = 5

Solution Approach

There are several ways to approach this problem:

Using Sorting: Sort the array and then directly access the kth element from the start for the kth minimum and kth element from the end for the kth maximum.
Using Heap: Utilize the heapq module to efficiently extract the kth smallest and largest elements without sorting the entire array.
Using Quickselect Algorithm: An optimized method based on the partitioning concept of quicksort, achieving an average time complexity of O(n).

Python Program

Method 1: Using Sorting

</>

Copy

# Function to find kth minimum and kth maximum using sorting
def kth_min_max_sort(arr, k):
    # Sort the array in ascending order
    arr_sorted = sorted(arr)
    kth_min = arr_sorted[k-1]      # kth minimum element
    kth_max = arr_sorted[-k]       # kth maximum element
    return kth_min, kth_max

# Sample Input
arr1 = [7, 10, 4, 3, 20, 15]
k = 3
kth_min, kth_max = kth_min_max_sort(arr1, k)
print("Using Sorting -> kth Minimum:", kth_min, ", kth Maximum:", kth_max)

Output:

Using Sorting -> kth Minimum: 7 , kth Maximum: 10

Method 2: Using Heap

The heapq module provides functions to efficiently retrieve the smallest or largest elements. Here, we use heapq.nsmallest() and heapq.nlargest().

</>

Copy

import heapq

# Function to find kth minimum and kth maximum using heap
def kth_min_max_heap(arr, k):
    kth_min = heapq.nsmallest(k, arr)[-1]
    kth_max = heapq.nlargest(k, arr)[-1]
    return kth_min, kth_max

# Sample Input
arr2 = [1, 2, 3, 4, 5, 6]
k = 2
kth_min, kth_max = kth_min_max_heap(arr2, k)
print("Using Heap -> kth Minimum:", kth_min, ", kth Maximum:", kth_max)

Output:

Using Heap -> kth Minimum: 2 , kth Maximum: 5

Method 3: Using Quickselect Algorithm

The Quickselect algorithm is an efficient way to find the kth smallest element without sorting the entire array. By modifying it slightly, we can also get the kth largest element.

</>

Copy

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):
    # base case
    if low == high:
        return arr[low]
    
    # Choose a random pivot index and move pivot to the end
    pivot_index = random.randint(low, high)
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    
    # Partition the array and get pivot index
    pi = partition(arr, low, high)
    
    # Check if pivot position is the kth element
    if k == pi:
        return arr[pi]
    elif k < pi:
        return quickselect(arr, low, pi - 1, k)
    else:
        return quickselect(arr, pi + 1, high, k)

# Function to find kth minimum and kth maximum using Quickselect
def kth_min_max_quickselect(arr, k):
    # Copy the array to avoid modifying the original list
    arr_copy = arr.copy()
    kth_min = quickselect(arr_copy, 0, len(arr_copy)-1, k-1)
    
    arr_copy = arr.copy()
    kth_max = quickselect(arr_copy, 0, len(arr_copy)-1, len(arr_copy)-k)
    
    return kth_min, kth_max

# Sample Input
arr3 = [7, 10, 4, 3, 20, 15]
k = 3
kth_min, kth_max = kth_min_max_quickselect(arr3, k)
print("Using Quickselect -> kth Minimum:", kth_min, ", kth Maximum:", kth_max)

Output:

Using Quickselect -> kth Minimum: 7 , kth Maximum: 10

Conclusion

We explored three methods to find the kth minimum and kth maximum elements in an array:

Sorting: Simple and easy to implement but with O(n log n) time complexity.
Heap: Efficient for scenarios where k is small relative to the array size, with O(n log k) complexity.
Quickselect: Offers an average time complexity of O(n) and is ideal for large datasets.

TutorialKart

Python – Find the Kth Maximum and Minimum Elements in an Array