Coding problem · Medium · Arrays & Hashing

Top K Frequent Elements

Medium Algorithms & data structures Most askedSeen at Amazon, Meta, Oracle, Yelp

Given an integer array nums and an integer k, return the k most frequent elements, in any order. The answer is guaranteed to be unique.

Example 1

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

Example 2

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

Constraints

1 <= k <= number of distinct values

Hints

Hint 1

Count frequencies first.

Hint 2

Bucket sort: index = frequency, so walking buckets from high to low gives the answer in O(n).

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) with buckets · Space O(n)

Count with a hash map, then avoid a full sort: put each value into buckets[count] and walk buckets from the highest frequency down until you have k values — O(n). A min-heap of size k (O(n log k)) is the other standard answer and is worth mentioning.

Reference solution

function topKFrequent(nums, k) {
  const count = new Map();
  for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [x, c] of count) buckets[c].push(x);
  const out = [];
  for (let c = buckets.length - 1; c > 0 && out.length < k; c--) out.push(...buckets[c]);
  return out.slice(0, k);
}

function topKFrequent(nums: number[], k: number): number[] {
  const count = new Map<number, number>();
  for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
  return [...count.entries()].sort((a, b) => b[1] - a[1]).slice(0, k).map(([x]) => x);
}

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    return [x for x, _ in Counter(nums).most_common(k)]

<?php

function topKFrequent(array $nums, int $k): array
{
    $count = array_count_values($nums);
    arsort($count);
    return array_slice(array_keys($count), 0, $k);
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        List<Integer>[] buckets = new List[nums.length + 1];
        for (var e : count.entrySet()) {
            if (buckets[e.getValue()] == null) buckets[e.getValue()] = new ArrayList<>();
            buckets[e.getValue()].add(e.getKey());
        }
        int[] out = new int[k];
        int i = 0;
        for (int c = buckets.length - 1; c > 0 && i < k; c--)
            if (buckets[c] != null) for (int x : buckets[c]) if (i < k) out[i++] = x;
        return out;
    }
}