178. Find the K Largest Elements in an Array

Given an array of n integers and a value k, print the k largest elements, in descending order, space-separated.

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 the k largest elements in descending order, space-separated.

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

The FINAL sort of just the k elements (not the whole array) is cheap since k is typically much smaller than n - don't confuse this small final sort with sorting the entire original array.

Print the k largest values in an array, in descending order. Brute force: Sort the whole array in descending order and take the first k elements - this costs O(n log n), more than necessary when a size-k heap gets the job done in O(n log k). Optimised: The same size-k min-heap technique used for finding just the KTH largest naturally generalizes to finding ALL k largest elements at once - the heap's final contents, after processing the whole array, are exactly the answer set, just needing a final sort (only k elements, so cheap) for the descending order.

Maintain a min-heap of size k. Process the array once: push each element onto the heap, and if the heap's size exceeds k, pop the smallest element off. After processing the whole array, the heap holds exactly the k largest elements, which can then be sorted (only k elements) into descending order for output. Since the heap never grows past size k, each insertion/removal costs O(log k) rather than O(log n), which is a real win when k is much smaller than n. Time: O(n log k) Space: O(k)

Sort the entire array in descending order using a comparison sort, then output the first k elements. This is simpler and asymptotically better than repeated max-scanning when k is a significant fraction of n, since the whole array is only touched O(log n) times per element instead of once per remaining scan, but it does unnecessary work sorting the n - k elements that are never needed. Time: O(n log n) Space: O(n)

Repeat k times: scan the entire array to find the current maximum among elements not yet picked, record it, and mark it as used. This directly produces the k largest elements in descending order by definition, but each of the k scans costs O(n), which adds up when k is large. Time: O(n * k) Space: O(n)

1. Maintain a min-heap capped at size k, exactly like the 'kth largest' problem. 2. For every element, push it in, popping the smallest if the heap exceeds size k. 3. At the end, the heap holds exactly the k largest elements - empty it out and print them in descending order.

Time: O(n log k) for building the capped heap, plus O(k log k) to sort the final k elements for output. Space: O(k), for the heap.

k = n (print the whole array sorted descending), k = 1, and arrays with duplicate values among the k largest.

Be ready to explain that this is a direct extension of the 'kth largest' problem - once you have the heap holding the k largest elements, printing all of them (versus just the top one) is a trivial final step.