Top K Frequent Elements

1. The obvious way

   Count, sort all distinct values by count, take k: O(n log n).

2. The key insight

   A value can appear at most n times, so make a shelf with n+1 slots where slot c holds the values that appeared exactly c times. Read the shelf from the top slot downward and collect k values: no sorting, O(n).

3. The algorithm
   1. Count each value on a tally sheet (dictionary).
   2. Make a shelf with one slot per possible count; put each value in the slot of its count.
   3. Read the shelf from the highest slot down, collecting values until you have k.

Watch it run

{1: 3, 2: 2, 3: 1}

from collections import Counter

def top_k_frequent(nums, k):
    tally = Counter(nums)                          # value -> how many times
    shelf = [[] for _ in range(len(nums) + 1)]     # shelf[c] = values seen c times
    for value, count in tally.items():
        shelf[count].append(value)
    answer = []
    for count in range(len(shelf) - 1, 0, -1):     # highest slot first
        for value in shelf[count]:
            answer.append(value)
            if len(answer) == k:
                return answer
    return answer

# alternative: heapq.nlargest(k, tally, key=tally.get)  -> O(n log k)

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.