LeetCode 347 · Medium · Arrays & Hashing

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements, in any order.

O(n)time
O(n)space
n+1frequency buckets

nums: 1–16 integers, −99 to 99 · k: 1 to the number of distinct values

1 · count→2 · bucket→3 · scan

nums phase 1 · pointer n walks the array

count hash map · value → times seen

freq bucket i holds the values seen exactly i times · bucket 0 stays empty

res collected from the highest bucket down · stop at k

public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new LinkedHashMap<>(); List<Integer>[] freq = new List[nums.length + 1]; for (int i = 0; i < freq.length; i++) { freq[i] = new ArrayList<>(); } for (int n : nums) { count.put(n, 1 + count.getOrDefault(n, 0)); } for (Map.Entry<Integer, Integer> e : count.entrySet()) { freq[e.getValue()].add(e.getKey()); } int[] res = new int[k]; int index = 0; for (int i = freq.length - 1; i > 0; i--) { for (int n : freq[i]) { res[index++] = n; if (index == k) { return res; } } } return res;}
n
—
c
—
i
—
freq[i]
—
res
—

Why it works

  1. The obvious way sorts: count, then sort the distinct values by count, O(n log n). A min-heap of size k gets O(n log k).
  2. A frequency is a small integer, between 1 and n. So use it as an array index: bucket i holds the values seen exactly i times. No comparisons, no sort.
  3. Scan from bucket n down to 1. Every value in a higher bucket is more frequent than every value in a lower one, so the first k values collected are the answer. Stop there: lower buckets are never touched.
  4. O(n) time: n counts, at most n values bucketed, n+1 buckets scanned. O(n) space for the map and the buckets.
  5. Pitfalls: size the array n + 1, not n, because a value can appear n times ([1] needs freq[1]). With ties at the boundary several answers are valid; LeetCode guarantees a unique one, so check by frequency, not by exact list. A plain HashMap iterates in no promised order, so this code uses LinkedHashMap to match the steps; any order inside a bucket is correct.
  6. Follow-up: for a stream, or when k is tiny, keep a min-heap of size k: a PriorityQueue ordered by count::get that polls its smallest entry whenever it grows past k. Quickselect is O(n) on average.