180. Top K Frequent Elements

Given an array of n integers and a value k, print the k elements that occur most frequently, ordered by descending frequency; break ties between equally frequent elements by printing the smaller value first.

Input: The first line contains an integer n. The second line contains n space-separated integers. The third line contains the integer k, the number of distinct elements to return (bounded by the number of distinct elements present). Output: Print the k most frequent elements, ordered by descending frequency with ties broken by the smaller value first, space-separated.

1 <= k <= number of distinct elements <= 10^5

Be precise about the exact tie-breaking rule (smaller value first among equally frequent elements) - a small detail that determines the exact expected output order when frequencies tie.

Find the k values that appear most often in an array, ordered by descending frequency. Brute force: Sort ALL distinct values by frequency directly and take the top k - this costs O(d log d), where d is the number of distinct values, more work than necessary when only the top k (not a full ordering of everything) is needed. Optimised: A heap capped at size k only ever needs to track the k MOST frequent values seen so far among the distinct values - discarding lower-frequency candidates immediately keeps the heap small, reducing the sorting cost from O(d log d) down to O(d log k).

Count frequencies with a hash map in one pass, then create an array of buckets indexed 1 through n where bucket[f] holds all distinct values that occur exactly f times, placing every distinct element into its frequency's bucket. Then walk the buckets from the highest possible frequency down to 1, and within each bucket that's reached, output its elements in ascending order (to satisfy the tie-break rule) until k elements have been printed in total. Since frequency can only range from 1 to n, this avoids any comparison-based sorting altogether and runs in linear time overall. Time: O(n) Space: O(n)

Count the frequency of every distinct value with a hash map in one pass, then repeat k times: scan the entire frequency map to find whichever remaining entry has the highest frequency (smallest value breaking ties), print it, and remove it from consideration. This directly implements 'take the top k' by repeated selection, but each of the k selection rounds costs a full scan over all distinct entries. Time: O(n + k * d) worst case O(n^2), where d is the number of distinct elements Space: O(d)

Count frequencies with a hash map in one pass, then sort the list of distinct elements once using a comparator that orders by descending frequency and, on ties, ascending value, and take the first k entries. Sorting once instead of repeatedly rescanning for the current maximum turns the k rounds of brute-force selection into a single O(d log d) sort, which is a clear improvement whenever k is a meaningful fraction of d. Time: O(n + d log d) Space: O(d)

1. Count every value's frequency with a hash map. 2. Maintain a heap of size k, ordered by (frequency, then value for tie-breaking) - pushing each distinct value and popping the least-priority one whenever the heap exceeds size k. 3. Empty out the final heap, ordering by descending frequency (and ascending value for ties).

Time: O(n) to count frequencies, plus O(d log k) to maintain the capped heap over d distinct values. Space: O(d), for the frequency hash map, plus O(k) for the heap.

k equal to the total number of distinct elements present, and multiple elements tied on frequency requiring the value-based tie-break.

Be ready to mention the 'bucket sort by frequency' alternative (since frequency can range only from 1 to n, you can bucket values by their exact frequency count and read off the top k directly) as an O(n) alternative when k is close to d - a nice non-heap-based optimization to know.