LeetCode · #347

Top K Frequent Elements Solution

Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order.

01
Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #347

🏗️

Pattern

Heap — k-th element + Hash Map

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique.

Example
Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2] // 1 appears 3 times, 2 appears 2 times — these are the top 2
Constraints
• 1 ≤ nums.length ≤ 10⁵ • -10⁴ ≤ nums[i] ≤ 10⁴ • k is in the range [1, number of unique elements] • The answer is guaranteed to be unique ↑ Frequencies are bounded by n — enables bucket sort
02
Section Two · Approach 1

Brute Force — Sort by Frequency O(n log n)

Count frequencies with a HashMap, then sort the entries by frequency in descending order. Take the first k elements from the sorted list.

Why it works

Sorting by frequency guarantees the most frequent elements come first. Taking the first k gives the correct answer.

Why we can do better
Problem: Sorting all unique elements costs O(m log m) where m is the number of distinct values. We only need the top k — a min-heap of size k gives O(m log k), and bucket sort exploits the bounded frequency range for O(n).
Java — Sort by Frequency
import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); for (int n : nums) freq.merge(n, 1, Integer::sum); return freq.entrySet().stream() .sorted((a, b) -> b.getValue() - a.getValue()) .limit(k) .mapToInt(Map.Entry::getKey) .toArray(); } }
Python — Sort by Frequency
from collections import Counter class Solution: def topKFrequent(self, nums: list[int], k: int) -> list[int]: count = Counter(nums) return [x for x, _ in count.most_common(k)]
MetricValue
TimeO(n log n) — dominated by sorting frequencies
SpaceO(n) — frequency map
03
Section Three · Approach 2

Bucket Sort — O(n)

The maximum possible frequency is n (the array length). Create an array of n+1 buckets where bucket[i] holds all elements with frequency i. Scan buckets from high to low, collecting elements until we have k.

💡 Mental model: Imagine a building with floors numbered 1 to n. Each floor represents a frequency count. You walk the building placing each unique number on the floor matching how many times it appears. To find the top k, you take the elevator to the top floor and walk down, picking up numbers from each floor until your basket has k items.
Algorithm — Bucket Sort by frequency
  • Step 1: Build a frequency map: num → count.
  • Step 2: Create List<Integer>[] buckets of size n+1. For each entry in the frequency map, add the number to buckets[count].
  • Step 3: Iterate from buckets[n] down to buckets[1], collecting elements into the result until result.size() == k.
  • Step 4: Return the result.
🎯 When to recognize this pattern:
  • Any time the problem asks for the top k or k-th largest/smallest and the metric is bounded (frequencies ≤ n, values in small range) — think bucket sort.
  • If the metric is unbounded, use a min-heap of size k for O(n log k).
  • This pattern appears in LC 347, LC 451 (Sort Characters by Frequency), and LC 692 (Top K Frequent Words).
Why bucket sort beats heap here:
  • A min-heap gives O(n log k) — excellent when k is small.
  • But bucket sort gives true O(n) because frequencies are naturally bounded by n.
  • The trade-off is O(n) extra space for the bucket array, but we already need O(n) for the frequency map.
04
Section Four · Trace

Visual Walkthrough

Trace through nums = [1, 1, 1, 2, 2, 3], k = 2:

Bucket Sort — frequency map → buckets → top k
INPUT ARRAY 1 1 1 2 2 3 Step 1 — Build frequency map { 1→3, 2→2, 3→1 } Step 2 — Fill buckets (index = frequency) BUCKETS freq=0: [] freq=1: [3] freq=2: [2] freq=3: [1] freq=4-6: [] Step 3 — Scan from highest bucket, collect k=2 elements bucket[3] → pick 1 (freq=3) → result = [1], need 1 more bucket[2] → pick 2 (freq=2) → result = [1, 2], done! bucket[1] → [3] — skipped, already have k elements Answer: [1, 2] ✓
Notice:
  • No sorting needed.
  • The bucket index is the frequency, so scanning from high to low naturally gives elements in frequency order.
  • We stop as soon as we have k elements — no wasted work.
05
Section Five · Implementation

Code — Java & Python

Java — Bucket Sort
import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); for (int n : nums) freq.merge(n, 1, Integer::sum); // Bucket index = frequency, value = list of nums with that frequency List<Integer>[] buckets = new List[nums.length + 1]; for (int i = 0; i < buckets.length; i++) buckets[i] = new ArrayList<>(); for (var e : freq.entrySet()) buckets[e.getValue()].add(e.getKey()); int[] result = new int[k]; int idx = 0; for (int i = buckets.length - 1; i >= 0 && idx < k; i--) for (int num : buckets[i]) // collect from highest freq down if (idx < k) result[idx++] = num; return result; } }
Python — Bucket Sort
from collections import Counter class Solution: def topKFrequent(self, nums: list[int], k: int) -> list[int]: freq = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for num, count in freq.items(): buckets[count].append(num) result = [] for i in range(len(buckets) - 1, 0, -1): result.extend(buckets[i]) if len(result) >= k: return result[:k] return result # unreachable
06
Section Six · Analysis

Complexity Analysis

ApproachTimeSpaceTrade-off
Sort by Frequency O(n log n) O(n) Straightforward; sort overhead for all unique elements
Min-Heap of size k O(n log k) O(n + k) Excellent when k ≪ n; heap maintains top-k invariant
Bucket Sort ← optimal O(n) O(n) True linear; exploits bounded frequency range
Why not heap?:
  • A min-heap of size k works well and is the go-to in many similar problems.
  • But here, frequencies are bounded by n — bucket sort avoids all log factors.
  • In an interview, mention both approaches: heap for the general case, bucket sort when the range is bounded.
07
Section Seven · Edge Cases

Edge Cases & Pitfalls

CaseInputWhy It Matters
k equals unique count[1,2,3], k=3Return all unique elements — every bucket contributes.
Single element[1], k=1Minimum input. Only one unique element, frequency 1.
All same[5,5,5,5], k=1One element at frequency n. Bucket[4] = [5].
Negative numbers[-1,-1,2], k=1HashMap handles negatives — frequency counting works the same.
Tied frequencies[1,1,2,2,3], k=2Guaranteed unique answer per constraints — but ties land in same bucket, both collected.
⚠ Common Mistake: Creating bucket array of size n instead of n+1. An element can appear n times, requiring bucket[n] — which needs array length n+1. Off-by-one here causes ArrayIndexOutOfBoundsException.

← Back to Arrays & Hashing problems