Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesMathReviewsAbout
Language
EnglishTürkçe

Hashing

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Prefix Sum →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 8
1
1
1
2
2
3
map1→32→23→1

K = 2

Top K frequent. Count frequencies first.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumhashingquick-selectheap-top-k

Top K Frequent Elements

Problem (restated)

Return the k most frequent elements in any order. The answer is unique.

Intuition

Count frequencies, then bucket by frequency so the densest buckets are at the end.

Approaches

Frequency buckets

Unverified
Time O(n)Space O(n)

Idea. Map value→count. buckets[c] holds values with count c. Scan buckets from high to low.

Walkthrough. [1,1,1,2,2,3], k=2 → 1 has freq 3, 2 has 2 → [1,2].

Trade-offs. Heap is O(n log k). Frequency is at most n, so scanning buckets is O(n) worst-case.

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

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

Template connection

Count with a hash map, then bucket by frequency (heap / quick-select also work).

Reflection