Counting Sort

Topic type: Technique-Based — a non-comparison integer sorting technique that distributes elements into indexed frequency buckets instead of comparing them.

LeetCode has fewer than 50 problems tagged Counting Sort directly. Depth: core algorithms, main patterns, key complexities.

See sorting.md for the full comparison of all sorting algorithms and when to choose between them.

---

Core Concepts

Counting sort — a non-comparison sort for integers (or values mappable to non-negative integers) in a bounded range [0, k). Achieves O(n + k) time by tallying frequency of each value, then reconstructing the sorted output from tallies.

Frequency array (count array) — an auxiliary array count of size k where count[v] holds how many times value v appears in the input. This is the core data structure of counting sort.

Prefix-sum step — transform count[v] from a frequency to a cumulative count: count[v] = number of elements ≤ v. This step converts the frequency array into a positional map, enabling stable placement of each element into the output.

Stability — equal elements appear in the original relative order in the output. Counting sort is stable when the output-filling loop traverses the input right-to-left and places each element at count[v] - 1, then decrements count[v]. Traversing left-to-right produces an unstable but still correct sort.

Value range k — the difference between maximum and minimum possible values (after offset normalisation). Counting sort is only practical when k = O(n); if k >> n, the count array dominates both time and space.

Offset normalisation — when values are not in [0, k) (e.g., they start at some minimum m), subtract m from every value before indexing into the count array, making the range [0, max - min].

---

Structural Invariants

---

Types / Variants

---

Key Algorithms

Basic counting sort (in-place reconstruction)

Tally each value into count, then overwrite the original array by writing each value v exactly count[v] times in order. — O(n + k) time, O(k) space.

count = [0] * (max_val + 1)
for v in arr: count[v] += 1
arr[:] = [v for v in range(max_val + 1) for _ in range(count[v])]

This variant is not stable — it does not preserve original element identity, only the multiset of values.

Stable counting sort

Three passes: (1) build frequency array, (2) prefix-sum to get positions, (3) fill output right-to-left so equal elements retain input order. — O(n + k) time, O(n + k) space.

for v in arr: count[v - offset] += 1          # pass 1: frequencies
for i in range(1, k): count[i] += count[i-1]  # pass 2: prefix sums
for v in reversed(arr):                        # pass 3: place right-to-left
    out[count[v - offset] - 1] = v; count[v - offset] -= 1

The right-to-left pass ensures the last occurrence of a duplicate is placed last — matching input order.

Counting sort as a frequency histogram query

Build count once; answer multiple "how many elements equal v" or "how many elements in [a, b]" queries in O(1) using count[v] or prefix[b] - prefix[a-1]. — O(n + k) build, O(1) per query.

This shifts the use case from sorting to frequency analysis — common in character-frequency and range-counting problems.

Radix sort digit pass (counting sort subroutine)

Radix sort applies stable counting sort once per digit position (LSD to MSD). Each pass sorts by one digit while preserving relative order from prior passes. — O(nk) total where k = number of digits.

See sorting.md for full radix sort coverage.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• k much larger than n. If values can be up to 10^9 but n is only 10^3, allocating a count array of size 10^9 causes OOM. Fix: compress values to [0, n) via coordinate compression before sorting, or use a hash map instead of an array.

• Forgetting offset when values are negative or start above 0. Indexing count[v] directly when v can be negative causes an index error or silent wrong placement. Always compute offset = min(arr) and index as count[v - offset].

• Off-by-one in prefix-sum step. The loop for i in range(1, k): count[i] += count[i-1] must start at index 1, not 0. Starting at 0 corrupts count[0].

• Right-to-left vs. left-to-right in output fill. Left-to-right fill is simpler but unstable. If the sort is used as a subroutine (e.g., in radix sort), left-to-right silently breaks correctness because equal-digit elements no longer preserve the order from the previous pass.

• Not re-initialising count between radix passes. Reusing the same count array across digit passes without zeroing it out produces wrong positional offsets. Always reset or re-allocate between passes.

• Empty input. min(arr) and max(arr) raise ValueError on an empty list. Guard with if not arr: return arr.

• All-identical values. Count array has a single non-zero entry. Output fill must still iterate all k positions; this is correct but inefficient if k >> 1. Not a bug, but worth noting for constant-factor performance.

• Modifying arr while iterating in the output-fill pass. In-place reconstruction overwrites arr while reading it. The safe version expands count directly without reading arr again; the stable version always uses a separate output array.

---

Implementation Notes

• Python's collections.Counter builds a frequency map in O(n) but is backed by a hash map, not an array. For small fixed alphabets (size 26 or a known small k), a plain list is faster.
• [0] * k is faster than collections.defaultdict(int) for dense integer ranges; use a defaultdict only when the range is sparse or unknown.
• itertools.accumulate applies the prefix-sum step in one line: count = list(accumulate(count)).
• Python lists are unbounded integers so there is no overflow risk in the count array itself, but be cautious when porting to Java/C++ with int count arrays over large n.
• For the size-26 character pattern, ord(c) - ord('a') is the canonical index; do not use ord(c) directly (indices 97–122 would waste the first 97 slots).

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Frequency and character sorting

• Sort Characters By Frequency (LC 451)
• Relative Sort Array (LC 1122)
• Sort Array by Increasing Frequency (LC 1636)

Anagram and permutation checks

• Valid Anagram (LC 242)
• Find All Anagrams in a String (LC 438)
• Permutation in String (LC 567)

Frequency-based analysis

• Top K Frequent Elements (LC 347) — frequency buckets indexed by count
• Top K Frequent Words (LC 692)
• Sort Colors (LC 75) — three-way partition; degenerate counting sort with k = 3

Missing / duplicate in bounded range

• Find All Numbers Disappeared in an Array (LC 448)
• Find the Duplicate Number (LC 287)

Harder applications

• Maximum Gap (LC 164) — bucket sort / pigeonhole; O(n) non-comparison sort
• H-Index (LC 274) — build citation count histogram; scan from right

Additional LeetCode Coverage

• Height Checker (LC 1051)

Clarification Questions to Ask

• What is the range of values? (Determines k and whether counting sort is feasible vs. coordinate-compressed or hash-map-based.)
• Are values guaranteed to be integers? (Counting sort does not apply to floats or arbitrary objects without a key function.)
• Does the problem require a stable sort, or is value order sufficient? (Unstable in-place reconstruction is simpler; stable requires an output array.)
• Can values be negative? (Requires offset normalisation; confirm whether min is known statically or must be computed.)
• Are there duplicate values, and does duplicate order matter? (Distinguishes stable from unstable variant.)

Common Interview Mistakes

• Allocating the count array as size max_val instead of max_val - min_val + 1, causing out-of-bounds when the minimum is non-zero.
• Performing the prefix-sum pass left-to-right correctly but then filling the output left-to-right, producing an unstable result and breaking radix sort.
• Using counting sort when k is on the order of 10^9 without coordinate compression, leading to OOM on otherwise straightforward problems.
• Reusing the count array across multiple radix passes without zeroing it, producing wrong sorted output on the second digit.
• Applying counting sort to floating-point values by truncating to integers, silently losing precision and misplacing elements.

Typical Follow-Up Escalations

• "Now values can be up to 10^9." → Coordinate-compress values to [0, n) first, or switch to comparison-based sort; counting sort is no longer practical.
• "Now sort the array in O(n) with O(1) extra space." → Three-way partition (Dutch National Flag) if k = 3; otherwise counting sort's O(k) space is unavoidable for general k.
• "Now also sort by a secondary key when values are equal." → Use stable counting sort; the secondary key is preserved by right-to-left output fill.
• "Now support online insertions between sorts." → Counting sort is a batch algorithm; switch to a balanced BST or sorted container for online updates.
• "What if duplicates should be removed?" → Skip the prefix-sum and output steps; a single pass over count yields the deduplicated sorted values.