Skip to main content

347. Top K Frequent Elements

mediumAsked at Cohere

Return the k most frequent elements in an array. Cohere asks this because frequency-based ranking is central to term-frequency scoring, vocabulary selection during tokeniser training, and log-aggregation pipelines.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Cohere SWE candidates report Top K Frequent Elements as a recurring medium problem in onsite rounds.
  • Blind (2025-12)— Multiple Cohere threads identify this as a standard heap/bucket-sort problem tested in coding screens.

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]

Explanation: 1 appears 3 times, 2 appears 2 times — top 2.

Example 2

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

Explanation: Single element.

Approaches

1. Frequency map + sort

Count frequencies with a Map, then sort entries by frequency descending and take the first k.

Time
O(n log n)
Space
O(n)
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  return [...freq.entries()]
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map(([num]) => num);
}

Tradeoff: Simple but O(n log n) due to sorting the full frequency map. Acceptable when n is small.

2. Bucket sort (O(n))

Create buckets indexed by frequency (1 to n). Place each element in its frequency bucket. Scan buckets from highest to lowest to collect k elements.

Time
O(n)
Space
O(n)
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) buckets[count].push(num);
  const result = [];
  for (let i = buckets.length - 1; i >= 1 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  return result.slice(0, k);
}

Tradeoff: O(n) time — optimal. Bucket index = frequency, so no comparison sort is needed. This is the answer to expect at Cohere when the interviewer asks for better than O(n log n).

Cohere-specific tips

Cohere interviewers routinely ask: 'Can you do better than O(n log n)?' — that is the cue to introduce bucket sort. Frame it as: 'The maximum possible frequency is n, so I can use frequency as a direct array index — no comparison sort needed.' Also mention that for very large k relative to n, a min-heap of size k is a classical alternative at O(n log k), which beats O(n log n) when k << n.

Common mistakes

  • Sorting descending but forgetting to reverse — JS sort is ascending by default.
  • Bucket array size of n instead of n+1 — frequency can be exactly n when all elements are the same.
  • Returning keys without .map() to extract numbers — Map entries are [key, value] pairs.
  • Not slicing to k after collecting from buckets — multiple elements may share the kth-largest frequency.

Follow-up questions

An interviewer at Cohere may pivot to one of these next:

  • Top K Frequent Words (LC 692) — same idea but with lexicographic tiebreaking.
  • Kth Largest Element in an Array — quickselect for O(n) average.
  • How would you maintain the top-k frequent elements in a real-time event stream?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

When does a min-heap beat bucket sort?

When k << n — a heap of size k processes n elements in O(n log k), which is better than O(n log n) sort but not quite O(n) bucket sort. If memory is constrained to O(k) auxiliary space, the heap is the right choice.

Why is bucket sort valid here?

The frequency domain is bounded: any element can appear at most n times. This bounded domain allows frequency as a direct array index, avoiding comparison-based sorting.

What if multiple elements tie at the kth frequency?

The problem guarantees a unique answer, so ties at exactly k are not possible in the given constraints.

Practice these live with InterviewChamp.AI

Drill Top K Frequent Elements and other Cohere interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →