Get started

Bucket Sort Coding Problems: 2 Questions with Solutions

2 bucket sort coding problems — 2 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 2-day plan.

  • Problems: 2
  • By difficulty: 2 medium
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Bucket sort drops each value into a bucket chosen by its key, then reads the buckets back in key order. When the key is bounded — a frequency can never exceed the array's length — the buckets are just an array indexed by the key, and sorting by it takes linear time instead of n log n. The problems here practise the form that comes up in interviews: count occurrences, bucket the values by their count, and read the buckets from the top to get the most frequent first.

How bucket sort works, step by step

0–910–1920–2930–3940–49numsbucketsoutput293411722812
Sorting numbers in a known range, with bucket sort. Example: nums = [29, 3, 41, 17, 22, 8, 12] (buckets of width 10)
  1. All 7 numbers lie in 0..49, so split that range into 5 buckets of width 10; a number's bucket is its value divided by 10, rounded down. The buckets are already in order, so only what is inside each needs sorting.
  2. 29 goes to bucket 29 / 10 = 2, which holds 20–29. Its value alone says where it goes: nothing is compared.
  3. 3 goes to bucket 3 / 10 = 0, which holds 0–9.
  4. 41 goes to bucket 41 / 10 = 4, which holds 40–49.
  5. 17 goes to bucket 17 / 10 = 1, which holds 10–19.
  6. 22 also falls in 20–29, so it lands under 29 in bucket 2; inside a bucket the order is still arrival order.
  7. 8 also falls in 0–9, so it joins 3 in bucket 0.
  8. 12 also falls in 10–19, so it joins 17 in bucket 1.
  9. Each bucket is sorted on its own: [17, 12] becomes [12, 17] and [29, 22] becomes [22, 29], while bucket 0 was already in order and bucket 3 is empty. Buckets are small, so this is cheap.
  10. Reading the buckets left to right gives [3, 8, 12, 17, 22, 29, 41], sorted, because every number in a bucket is below every number in the next. With values spread evenly over k buckets this is O(n + k) on average.

Bucket Sort study plan

All 2 Bucket Sort problems (2 medium) over 2 days, about 1 h 25 min in all — the pattern first, then easiest to hardest. Then move on to Binary Search.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Next topic: Binary Search

Bucket Sort: the essentials

When to reach for it

Ordering by a key whose range is small and known: a frequency (1 to n), a score out of 100, a character. "Top k frequent" and "sort by frequency" are the interview forms; the textbook one spreads evenly distributed real numbers into equal slices of their range. For keys up to 10⁹ and a small n, a comparison sort or a heap is simpler.

The pattern

Count, then make one list per possible key — for frequencies, indices 0 to n — and append each value to its count's list. Reading from the top index down gives the most frequent first; take the first k. A tie rule such as "smaller value first" needs each bucket sorted, or the values appended in that order. One bucket per small integer value is Counting Sort.

from collections import Counter

def top_k_frequent(nums, k):        # most frequent first; ties in any order
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]    # index = frequency
    for x, c in count.items():
        buckets[c].append(x)
    out = []
    for f in range(len(nums), 0, -1):   # highest frequency first
        out.extend(buckets[f])
    return out[:k]

Cost

Counting, filling and reading are each O(n): O(n) time and space, against O(n log n) for sorting by count and O(n log k) for a heap. The textbook version averages O(n) but degrades to sorting one crowded bucket.

Common mistakes

  • Sizing the buckets by the number of distinct values rather than n + 1, when one value can make up the whole input.
  • Bucketing by value instead of by count, which needs a slot for every possible value.
  • Reading the buckets from index 0, least frequent first.
  • Ignoring the tie rule, which Top K Frequent Elements and Sort Characters By Frequency both state.

Start with

All bucket sort problems

Medium (2)

Next topic: Binary Search