FAANG · LeetCode #347

Top K Frequent Elements — three-stage drill

1The ProblemMedium

Top K Frequent Elements

Return the k elements that appear most often.

Examples

[1,1,1,2,2,3], k=2→ [1,2]

constraintThe answer is unique for the given k.

2The PatternTIME O(n) · SPACE O(n)

Arrays & Hashing

Trade space for time: a hash map turns 'have I seen this?' into an O(1) lookup.

Problems using this pattern

3The SolutionRESULT → [1, 2]

Step through it

count: 1 → 1×

Step 1 / 7

Python▎count, then take the k largest

1def topKFrequent(nums, k):
2    freq = {}
3    for x in nums:
4        freq[x] = freq.get(x, 0) + 1
5    return sorted(freq, key=freq.get, reverse=True)[:k]

why it worksFirst tally each value's frequency in a hash map (one pass). Then take the k keys with the largest counts. Sorting the map by count is O(n log n); bucketing by frequency (index = count) gets it to O(n).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Top K Frequent Elements — three-stage drill