Count array
- Algorithms course
- Intermediate
- Lesson 14/80
- 4 min
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.
Practice 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])).
Starter code
def build_count(arr):
# Build count arraySample 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]))Expected output
[0, 2, 1, 1]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Frequency increment
count[____] += 1count[arr[i]] += 1Explanation: arr[i] is right.
2 Count array: match the terms
| Term | Meaning |
|---|---|
Count array |
Frequency |
Cumulative |
Position |
Place backward |
Stable |
Cost |
O(n+k) |
3 What is the cumulative sum for?
- Reduce memory
- Slow down
- Positioning Correct answer
- Comparison
Explanation: Positioning