4. Kth Max and Min Element of an Array

Given an array of n integers and a value k, print the kth largest element followed by the kth smallest element (1-indexed), separated by a space.

Input: The first line contains n and k, space-separated. The second line contains n space-separated integers. Output: Print the kth largest element followed by the kth smallest element, separated by a space.

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

The index formulas (k-1 for kth smallest, length-k for kth largest) are easy to mix up under pressure - anchor them by mentally checking k=1 (smallest should be at index 0; largest should be at the very last index) before trusting the general formula.

Find the kth largest number and the kth smallest number in a list, both counting from 1. Brute force: Repeatedly scan for and remove the current maximum k times to find the kth largest (and similarly for the minimum) - this works but costs O(n*k), less efficient than sorting once for both answers. Optimised: A single sort gives you INSTANT access to both the kth largest and kth smallest via simple index arithmetic - no need for two separate repeated-scanning processes when one sort answers both questions at once.

Use quickselect (Hoare's selection algorithm): pick a random pivot, partition the array in-place around it as in quicksort, and recurse only into the one side that must contain the desired rank, discarding the other side entirely without ever sorting it. Running this once for rank n-k gives the k-th largest and once for rank k-1 gives the k-th smallest. Because only one side of each partition is ever explored, the expected work is linear rather than the heap approach's n log k or the sort's n log n, at the cost of an unlikely but real O(n^2) worst case with adversarial pivots. Time: O(n) average Space: O(1)

Sort the entire array in ascending order, then the k-th smallest element is directly at index k-1 and the k-th largest is at index n-k. This is simple and always correct, but it does more work than necessary since fully ordering the whole array is far more information than is actually needed to answer just two order-statistic queries. Time: O(n log n) Space: O(n)

To find the k-th largest, scan the array while maintaining a min-heap capped at size k, pushing each element and popping the smallest whenever the heap exceeds size k; the heap's root is then the k-th largest. Symmetrically, use a max-heap capped at size k to find the k-th smallest. This avoids sorting the entire array, doing work proportional to n but only log k per element instead of log n, which is a real improvement whenever k is much smaller than n. Time: O(n log k) Space: O(k)

1. Sort the array in ascending order. 2. The kth SMALLEST element is simply at position (k-1) in this sorted array (since sorting ascending puts the smallest first). 3. The kth LARGEST element is at position (length - k) in the same sorted array (counting backward from the end). 4. Print both values.

Time: O(n log n), dominated entirely by the sort - both index lookups afterward are instant. Space: O(1) extra space beyond whatever the sort itself requires (or O(n) if the sort isn't in-place).

k = 1 (returns the overall max and min); k = n (the kth largest becomes the array's minimum and the kth smallest becomes its maximum); and n = 10^5 (largest, confirming a sort-based lookup is efficient enough).

Be ready to mention that a heap-based approach can find just the kth largest (or smallest) alone in better than O(n log n) time when you only need ONE of the two answers, not both - sorting is the simplest correct approach when you need both.