Bucket Sort Problems
6 Bucket Sort LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Choose buckets that match the key range
Bucket sorting groups items by a key before reading the groups in order. For Top K Frequent Elements, the useful key is frequency: an item seen f times belongs in bucket f. This is different from placing arbitrary numeric values into equal-width ranges and sorting inside each range.
When to use it
Frequency buckets work well when the input has n items, because every frequency is between 1 and n. Range buckets are useful when the value range and distribution make buckets manageable; they do not guarantee linear time for arbitrary data.
Worked example
Values: [4, 4, 2, 2, 2, 9]. Find the two most frequent values.
- Count occurrences: 2 appears three times, 4 twice, and 9 once.
- Put 2 in bucket 3, 4 in bucket 2, and 9 in bucket 1.
- Read buckets from frequency 6 down to 1 and stop after collecting two values.
The selected values are [2, 4]. Their numeric order is irrelevant; frequency controls the order.
Time and space
Counting with a hash map, allocating n + 1 frequency buckets, and scanning them takes expected O(n) time and O(n) space. A range-bucket sort also pays for sorting within buckets; one crowded bucket can dominate its running time.
Mistakes to check
- Do not allocate an array spanning enormous raw values just because the input is small. Frequency buckets use counts, not the values themselves.
- Equal frequencies need the problem's tie rule. Top K Frequent Words, for example, requires lexical ordering within a frequency group.
- For Maximum Gap, derive bucket width and the empty-bucket argument from the value range; a frequency-bucket solution answers a different question.
Further reading: NIST Dictionary of Algorithms: bucket sort
Guide reviewed .