172. Kth Smallest Element in an Array

Given an array of n integers and a value k, find the kth smallest element (k=1 means the smallest).

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the integer k. Output: Print a single integer - the kth smallest element.

1 <= k <= n <= 10^5

This is the exact mirror image of 'Kth Largest Element in an Array' - recognizing that the two problems are solved by simply swapping which type of heap you use is a great pattern-matching signal.

Find the kth smallest value in an array, where k=1 means the single smallest. Brute force: Sort the whole array ascending and index directly into position k-1 - this costs O(n log n), more work than necessary for just finding the kth value. Optimised: A max-heap capped at size k only ever needs to track the k SMALLEST elements seen so far - anything larger than the heap's current maximum can never be among the k smallest, so it's safely discarded immediately.

Apply the Quickselect algorithm: pick a pivot (ideally randomly, to avoid worst-case bias), partition the array around it like in quicksort, and recurse only into the one side (left or right of the pivot) that must contain the kth smallest element, discarding the other side entirely without ever sorting it. Because only one partition is recursed into instead of both, the expected work shrinks geometrically each round, giving expected linear time overall while sorting the whole array is unnecessary. Time: O(n) average, O(n^2) worst case Space: O(1)

Maintain a max-heap that never holds more than k elements: push each array element onto the heap, and whenever its size exceeds k, pop the largest element off. After processing the whole array, the heap's top (largest remaining element) is exactly the kth smallest overall, since the heap always retains the k smallest values seen so far. This avoids sorting the whole array and instead pays only O(log k) per element, which is cheaper than full sorting whenever k is much smaller than n. Time: O(n log k) Space: O(k)

Sort the entire array in ascending order and return the element at index k-1. This is simple and always correct, but it fully orders the array even though only one specific rank is actually needed. Time: O(n log n) Space: O(n)

1. Maintain a max-heap capped at size k. 2. For every element, push it into the heap; if the heap grows past size k, pop the largest (discarding it). 3. After processing the whole array, the heap's top (its largest remaining element) is exactly the kth smallest.

Time: O(n log k) - each element triggers at most one push and one pop on a heap of size at most k. Space: O(k), for the heap.

k = 1 (the minimum), k = n (the maximum), and arrays with duplicate values.

Be ready to connect this directly to its mirror-image sibling 'Kth Largest Element' - the exact same technique, just swapping min-heap for max-heap.