2 questions using this pattern
Exploit bounded value ranges to achieve linear time sorting or selection by using values as array indices.
Imagine sorting mail into numbered PO boxes. Instead of comparing letters to each other, you simply look at the box number and drop it in. If you have 100 boxes, sorting 1000 letters takes 1000 steps, not 1000 x log(1000).
When values are bounded within a known range [0, k], you can use the value itself as an index into an array of "buckets." This converts comparison-based O(n log n) sorting into O(n + k) counting operations.
The key insight: bounded values = direct addressing is possible.
Use this skeleton as a starting point for problems using this pattern:
def bucket_sort_approach(nums: list[int], k: int) -> list[int]:
# Create buckets indexed by value/frequency
n = len(nums)
buckets = [[] for _ in range(n + 1)] # n+1 for frequency 0 to n
# Count frequencies
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
# Place elements in frequency buckets
for num, freq in count.items():
buckets[freq].append(num)
# Collect from highest frequency
result = []
for i in range(n, 0, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return resultLook for these keywords and patterns in problem descriptions:
Heap gives O(n log k) but bucket sort gives O(n) when frequencies are bounded. Always check if values/frequencies have a known upper bound.
Fix:
Ask: "What's the maximum possible value/frequency?" If bounded by n, use bucket sort.
Creating n buckets for frequencies 0 to n-1 misses frequency n
(when all elements are identical).
Fix:
Create n + 1 buckets to handle frequencies from 0 to n inclusive.
Use frequency as bucket index, collect from highest
Examples: top-k-frequent-elements
Three buckets for 0, 1, 2
Examples: sort-colors
Citation count buckets
Examples: h-index
Master the pattern with these representative problems.
Explore similar techniques:
Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.
A data structure that efficiently maintains the minimum or maximum element, supporting O(log n) insertion and extraction. Heaps are essential when you repeatedly need to access the smallest or largest element from a changing set.