Top K Frequent Elements

Return the k most frequent elements of an array, in any order.

A way to picture it

It's a talent-show vote count. First, tally everyone's votes. Then, instead of sorting all the contestants, drop each one into a bucket labelled with their vote count. Read the buckets from most votes down until you have k winners.

How to approach it

Count frequencies, then bucket-sort by frequency (bucket index = count). Walk the buckets from high to low, collecting k values.

Example

Input: {"nums":[1,1,1,2,2,3],"k":2}. Output: [1,2].

Complexity: O(n) time and O(n) space. A frequency can't exceed n, so there are only n + 1 buckets.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.