Arrays
Episode 8 Top K Frequent Elements
▶ This video is coming to YouTube soon.
LeetCode 347, Top K Frequent Elements, solved on screen. We start with three examples, then count every number with a HashMap and sort the numbers by their count: simple, but the sort makes it O(n log n). Then we beat the follow-up with bucket sort: a count is never bigger than n, so an array of n + 1 buckets, indexed by count, puts the numbers in order without sorting. Read the buckets from the top until you have k numbers: O(n).
What you'll learn
- What the problem asks, through three worked examples
- Counting with a HashMap and merge
- Count and sort: O(n log n) time, O(n) space
- The key idea: an array of buckets indexed by count
- Bucket sort: O(n) time, O(n) space
Chapters
- 0:00The problem
- 0:14Examples
- 0:50Count and sort, visualized
- 1:34Count and sort: the code
- 1:47Count and sort, line by line
- 2:31Bucket sort: the idea
- 2:50Bucket sort, visualized
- 3:44Bucket sort: the code
- 3:59Bucket sort, line by line
- 4:51Comparing the approaches