347. Top K Frequent Elements

At a Glance

• Topic: arrays-hashing
• Pattern: Top-K / Heap (bucket sort variant)
• Difficulty: Medium
• Companies: Amazon, Google, Meta, LinkedIn, Bloomberg
• Frequency: High
• LeetCode: 347

Problem (one-liner)

Given an integer array numbers and an integer k, return the k most frequent elements. Order in the output is not specified unless the problem says so.

Core Basics

• Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
• Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
• Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

• Why brute hurts: name the repeated work or state explosion in one sentence.
• Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

• One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

• "Top k frequent", "k most common"
• Frequency count + selection (heap, bucket, or quickselect)

Study Pattern (SDE3+)

• 0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — count with map, sort all unique by count — O(n + u log u) time.
• Better — min-heap of size k on (count, value) — O(n log k) time / O(n) space.
• Optimal (interview favorite) — bucket by frequency: index = frequency, O(n) time / O(n) space; or heap O(n log k).

Optimal Solution

Go

package main

func topKFrequent(numbers []int, topK int) []int {
	counts := make(map[int]int)
	for _, value := range numbers {
		counts[value]++
	}
	buckets := make([][]int, len(numbers)+1)
	for value, frequency := range counts {
		buckets[frequency] = append(buckets[frequency], value)
	}
	result := make([]int, 0, topK)
	for frequency := len(buckets) - 1; frequency >= 0 && len(result) < topK; frequency-- {
		for _, value := range buckets[frequency] {
			result = append(result, value)
			if len(result) == topK {
				return result
			}
		}
	}
	return result
}

JavaScript

function topKFrequent(numbers, topK) {
	const counts = new Map();
	for (const value of numbers) {
		counts.set(value, (counts.get(value) || 0) + 1);
	}
	const buckets = Array.from({ length: numbers.length + 1 }, () => []);
	for (const [value, frequency] of counts) {
		buckets[frequency].push(value);
	}
	const result = [];
	for (let frequency = buckets.length - 1; frequency >= 0 && result.length < topK; frequency--) {
		for (const value of buckets[frequency]) {
			result.push(value);
			if (result.length === topK) {
				return result;
			}
		}
	}
	return result;
}

Walkthrough

Input: numbers = [1,1,1,2,2,3], topK = 2

Invariant: bucket frequency holds all values that appear exactly frequency times.

Edge Cases

• k equals number of distinct elements → return all distinct.
• Single value repeated n times, k = 1.
• All unique → any k values (each frequency 1).

Pitfalls

• Using max-heap incorrectly (min-heap of size k is standard for top-k by frequency).
• Off-by-one on bucket size (len(numbers)+1).

Similar Problems

• 215. Kth Largest Element in an Array — selection / heap.
• 238. Product of Array Except Self — array indexing tricks.
• 001. Two Sum — frequency maps.

Variants

• Break ties by smaller value.
• Stream of elements — use heap or counting sketch.

Mind-Map Tags

#heap #bucket-sort #frequency #hashmap #top-k