Get started

Counting Sort Coding Problems: 8 Questions with Solutions

8 counting sort coding problems — 6 easy · 2 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 3-day plan.

  • Problems: 8
  • By difficulty: 6 easy · 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

When the values live in a small known range, counting how many of each and writing them back out sorts in linear time. The problems here are the ones where that range is given — digits, letters, bounded scores — and a comparison sort would be doing more work than the input deserves.

How counting sort works, step by step

nums401132130445countvalue1021021324output001112334445
Sorting small whole numbers, with counting sort. Example: nums = [4, 1, 3, 1, 0, 4] (values 0 to 4)
  1. Every value lies between 0 and 4, so instead of comparing numbers, keep one counter per possible value: 5 counters, all starting at 0.
  2. nums[0] = 4, so count[4] goes up to 1. The value itself is the index of its counter, so no other number is looked at.
  3. nums[1] = 1, so count[1] goes up to 1, still without comparing anything.
  4. nums[2] = 3, so count[3] goes up to 1, found straight from its value.
  5. nums[3] = 1 again, so count[1] becomes 2: a repeat only raises its counter.
  6. nums[4] = 0, so count[0] goes up to 1, its counter picked by the value alone.
  7. nums[5] = 4 again, so count[4] becomes 2: a repeat only raises its counter.
  8. Now walk the counters from the smallest value up. count[0] = 1, so write one 0 into output[0]; going in value order is what makes the output sorted.
  9. count[1] = 2, so write 2 copies of 1 into output[1..2].
  10. count[3] = 1, so write one 3 into output[3]. count[2] is 0, so 2 is skipped.
  11. count[4] = 2, so write 2 copies of 4 into output[4..5].
  12. The output [0, 1, 1, 3, 4, 4] is sorted without comparing two numbers. One pass to count and one over the 5 counters to write: O(n + k) time for n = 6 numbers whose values span k = 5.

Counting Sort study plan

6 of the 8 Counting Sort problems (4 easy and 2 medium) over 3 days, about 2 h 45 min in all — the pattern first, then easiest to hardest. After that, the other 2 in the full list below are practice at your own pace. Then move on to Bucket Sort.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

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

Next topic: Bucket Sort

Counting Sort: the essentials

When to reach for it

The constraints bound the values tightly — 0 <= nums[i] <= 1000, lowercase letters, heights up to 100, scores capped at n — and the task needs sorted order or ranks. When the value range k is no larger than about n, counting beats comparison sorting; when k dwarfs n (values up to 10⁹), it does not.

The pattern

Count each value into an array indexed by the value, then either write the values back in order or turn the counts into running totals. After the running sum, count[v] is the number of elements less than or equal to v, which hands every element its rank directly. To sort records stably by a small key, compute the running totals and place records from the back of the input, each at its key's next free slot counting down.

def counting_sort(nums, max_value):    # 0 <= x <= max_value
    count = [0] * (max_value + 1)
    for x in nums:
        count[x] += 1
    out = []
    for v, c in enumerate(count):
        out.extend([v] * c)
    return out

Cost

O(n + k) time and O(k) extra space for values in [0, k]. H-Index uses the same idea with values capped at n, because a citation count above n counts the same as n.

Common mistakes

  • Allocating max_value + 1 slots when values can be negative; shift every value by the minimum first.
  • Using it when k is far larger than n, so the count array dominates both time and memory.
  • An off-by-one between "less than" and "less than or equal" when reading ranks from the running totals.
  • Placing records front to back against running totals that point at each key's last slot, which reverses equal keys and loses stability.

Start with

All counting sort problems

Easy (6)

Medium (2)

Companies that ask counting sort problems

  • Amazon 8 problems on counting sort
  • Adobe 4 problems on counting sort
  • Google 4 problems on counting sort
  • Microsoft 2 problems on counting sort
  • Bloomberg 1 problem on counting sort
  • Meta 1 problem on counting sort

Next topic: Bucket Sort