Skip to main content

347. Top K Frequent Elements

medium

Return the k most frequent elements in an array. Combines counting (hash map) with a top-k selection — either a min-heap of size k or O(n) bucket sort, depending on which trick the interviewer wants to see.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Examples

Example 1

Input
nums = [1,1,1,2,2,3], k = 2
Output
[1,2]

Example 2

Input
nums = [1], k = 1
Output
[1]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Step 1: hash-map count every element's frequency.

Hint 2

Step 2 (heap): push each (count, num) into a min-heap of size k, popping when it exceeds k. The heap's contents are the top k. O(n log k).

Hint 3

Step 2 (bucket sort): build buckets[freq] -> list of nums; iterate from highest freq down, collecting until you have k. O(n).

Solution approach

Reveal approach

Two clean approaches; both start with a hash map count of num -> frequency. Min-heap version: iterate map; push (freq, num) onto a min-heap. If heap size exceeds k, pop. After processing, the heap holds the k most-frequent — extract them. O(n log k). Bucket-sort version (slicker, O(n)): create buckets[freq] for freq in 1..n, each holding a list. Walk the map and append num to buckets[freq]. Walk buckets from index n down to 1, flattening into a result; stop when result has k entries. The bucket version exploits the fact that freq is at most n.

Complexity

Time
O(n) with bucket sort, O(n log k) with heap
Space
O(n)

Related patterns

  • hash-table
  • heap
  • bucket-sort
  • counting

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Top K Frequent Elements and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →