Kth Largest / Smallest Element

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array. Similarly, the kth smallest element can be found.

Example: nums = [3,2,1,5,6,4], k = 2 → Output: 5 (2nd largest)

Approach 1: Sorting (Simple)

Explanation: Sort the array and pick the kth largest/smallest directly.

Time Complexity: O(n log n)

Space Complexity: O(1) or O(n) depending on sort implementation 

sort(nums)
return nums[n-k]  # kth largest
return nums[k-1]  # kth smallest
Heap Sort Flowchart

Approach 2: Min Heap (Optimal for Kth Largest)

Explanation: Maintain a min-heap of size k. Push elements. The root is the kth largest.

Time Complexity: O(n log k)

Space Complexity: O(k)

create empty min-heap
for num in nums:
    add num to heap
    if heap size > k:
        remove min element
return heap root
Heap Sort Flowchart

Approach 3: Quickselect (Optimal Average)

Explanation: Use partitioning like in quicksort to find kth largest without full sort.

Time Complexity: O(n) average, O(n^2) worst-case

Space Complexity: O(1)

choose pivot
partition array into < pivot and >= pivot
if k in right partition:
    recurse on right
elif k in left:
    recurse on left
else:
    return pivot
Heap Sort Flowchart