Count array

Build a count array for the value range.

Count array

The count array holds the frequency of each key. count[i] is how many times value i appears in the array.

First, all count is zeroed (size k = max(arr)+1). Then for each element count[arr[i]] += 1.

This step is O(n + k). For negative values an offset with min is applied.

Cumulative sum

If we turn the count array into a cumulative sum, count[i] now tells how many elements are less than or equal to i. This gives each element's position in the sorted array.

Cumulative sum: count[i] += count[i-1], i from 1 to k-1.

This step is critical for a stable sort; elements are placed backwards.

Exercise Build count array

Write build_count(arr). Return a count array over 0..max(arr). Print [0, 2, 1, 1] with print(build_count([1, 3, 1, 2])).

Show example solution

def build_count(arr):
    # Build count array
    count = [0] * (max(arr) + 1)
    for x in arr:
        count[x] += 1
    return count
print(build_count([1, 3, 1, 2]))

Test yourself

Frequency increment
```
count[____] += 1
```
Show answer
```
count[arr[i]] += 1
```
Count array: match the terms

Count array

Frequency
Cumulative

Position
Place backward

Stable
Cost

O(n+k)
What is the cumulative sum for?
- Reduce memory
- Slow down
- Positioning
- Comparison
Show answer

Positioning — Positioning

Next lesson: Output array

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies