K Most Frequent Values
Problem
Given a list of whole numbers and a count k, return the k values that appear most often. Order the result from most to least frequent, and when two values appear equally often, put the smaller value first. You may assume k is at least 1 and no larger than the number of distinct values.
Examples
Input: values = [4, 1, 4, 2, 1, 4, 3], k = 2
Output: [4, 1]
Why: 4 appears three times and 1 twiceInput: values = [7, 8, 9, 8, 9], k = 1
Output: [8]
Why: 8 and 9 tie at two each, and 8 is smallerInput: values = [5], k = 1
Output: [5]
Why: edge case, a single valueHints
0 / 3
Counting is the easy half. The real question is how to pick the k best counts without sorting every distinct value.
Keep only k candidates at a time. The one you need quick access to is the weakest candidate, because that is the one a newcomer has to beat.
Count with a dictionary, then push (count, -value) pairs into a min-heap and pop whenever it grows past k. The negated value makes a larger value the weaker one on ties. Finally sort the survivors from strongest to weakest.
Solution
A dictionary counts each value in one pass. A min-heap capped at k then holds the best candidates so far, with the weakest at the root, so each new value costs one push and at most one pop. Storing the pair (count, -value) makes the heap treat fewer appearances as weaker and, on equal counts, a larger value as weaker, which matches the required tie rule. Sorting the k survivors in reverse gives the final order. Time is O(n + d log k) for d distinct values, and space is O(d).
import heapq
from collections import Counter
def most_frequent(values, k):
keep = [] # min-heap of the k strongest (count, -value)
for v, c in Counter(values).items():
heapq.heappush(keep, (c, -v))
if len(keep) > k:
heapq.heappop(keep) # the weakest keeper leaves
return [-nv for c, nv in sorted(keep, reverse=True)]
print(most_frequent([4, 1, 4, 2, 1, 4, 3], 2)) # -> [4, 1]
print(most_frequent([7, 8, 9, 8, 9], 1)) # -> [8]
print(most_frequent([5], 1)) # -> [5]Stuck on the idea rather than the code? Top K in a Stream covers it.