Skip to main content

79. Top K Frequent Elements

mediumAsked at Salesforce

Return the k most frequent elements. Salesforce uses this for top-k report queries — they grade on heap vs bucket-sort recognition.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses this for top-k report queries (top accounts, top products).
  • Blind (2025-11)— Recurring on Salesforce backend onsites.

Problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

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]

Approaches

1. Sort by frequency

Count, sort entries by frequency descending, take top k.

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

Tradeoff: Sort is O(n log n) — explicitly forbidden by the problem.

2. Bucket sort by frequency

Count. Place each value in buckets[frequency]. Walk buckets right-to-left collecting k values.

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

Tradeoff: True O(n). The buckets are indexed by frequency (which is bounded by n), so this exploits the bounded-range trick.

Salesforce-specific tips

Salesforce uses top-k reports everywhere (top deals, top reps, top accounts). They specifically grade on whether you can achieve sub-n-log-n via bucket sort. Bonus signal: discuss that heap-of-size-k is O(n log k) — better than sort but slightly worse than bucket sort for top-k.

Common mistakes

  • Using sort directly — explicitly disallowed by the time complexity requirement.
  • Using a max-heap of all elements — O(n + k log n), works but heap-of-size-k is O(n log k) which is better.
  • Bucket-indexing by value instead of frequency — value range can be huge; frequency range is bounded by n.

Follow-up questions

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

  • Top K Frequent Words (LC 692) — ties broken alphabetically.
  • Kth Largest Element (LC 215).
  • Top k via Quickselect — O(n) average.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is bucket sort O(n)?

Because frequencies are bounded by n (a value can appear at most n times). Creating n+1 buckets is O(n) and placing each unique value is O(unique) <= O(n).

Min-heap or max-heap?

Min-heap of size k: maintain only the top k by frequency. Push, pop if size > k. Final heap is the answer.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →