Frequency arrays and counting

Counting is everywhere in competitive programming. How many times does a character appear? How many players scored exactly five goals? Which digit shows up most often in a number? Instead of searching the data over and over, you can count everything in one pass with a frequency array.

A frequency array stores a count for each possible value. If you know the range of values ahead of time, you can build an array where the index represents the value and the stored number is the count. This method is fast and simple.

The idea of a frequency array

Imagine you are tracking book titles. You see a list of book IDs, and each ID is a number from 0 to 99. You want to count how many times each ID appears.

A frequency array has 100 slots, one for each ID. Start with all slots at zero. As you read each ID, add one to the slot for that ID. After one pass through all the data, the slots hold the answer.

Here is a small example. The IDs are: 5, 2, 5, 7, 2, 5.

Start with a frequency array of size 100, all zeros. Read each ID in order. When you see 5, add 1 to freq[5]. Now freq[5] is 1. The next ID is 2, so add 1 to freq[2]. The next ID is 5 again, so add 1 to freq[5]. Now freq[5] is 2. Continue through all six IDs.

After one pass, freq[2] is 2 because ID 2 appeared twice, freq[5] is 3 because ID 5 appeared three times, and freq[7] is 1 because ID 7 appeared once. Every other slot is still 0.

One pass through the data, one addition per value. Fast.

Why is this faster than alternatives? A dictionary also counts, but it must compute a hash of the key, look up the key in the table, and update the value. An array just uses the value as an index directly. Array access is a single memory lookup with no computation. This difference matters on large datasets. If you count millions of items, the array approach is noticeably faster than a dictionary.

Counting characters in a string

Consider counting the letters in a word. Your input is a single word, and you must print how many times each letter a through z appears.

Take the word "banana". It has six letters. The letter a appears three times, b and n each appear once, and the other letters do not appear.

Build a frequency array of size 26, one slot for each letter a through z. Loop through the word. For each character, subtract the ASCII value of 'a' to get an index from 0 to 25, then add one to that slot.

1word = input()2freq = [0] * 263
4for char in word:5    if 'a' <= char <= 'z':6        index = ord(char) - ord('a')7        freq[index] += 18
9for i in range(26):10    if freq[i] > 0:11        letter = chr(ord('a') + i)12        print(f"{letter}: {freq[i]}")

banana

a: 3
b: 1
n: 2

This prints each letter and its count. The character ord() function gives the ASCII value. The chr() function does the reverse, building a character from its ASCII value.

Step through the process below on a different word, "cabbage". Watch how each letter increments its own slot in the frequency array while every other slot stays at 0.

Counting digits in a number

Another common use is counting digits. Digits range from 0 to 9, so your frequency array has exactly 10 slots.

Suppose the number is 31241314. You want to count how many times each digit appears. Convert the number to a string, then loop through the characters. For each character, convert it back to a digit and increment the corresponding slot.

1number = "31241314"2freq = [0] * 103
4for char in number:5    digit = int(char)6    freq[digit] += 17
8print("Digit counts:")9for d in range(10):10    if freq[d] > 0:11        print(f"  {d}: {freq[d]}")

This counts digits in one pass. The digit 1 appears three times, digit 3 appears twice, digit 4 appears twice, and so on.

The advantage of frequency arrays grows with the size of the data. Looping through millions of items and updating an array index is a single memory write per item, with no hashing and no comparisons. A dictionary or a sort would do more work per item over the same data. Frequency arrays get this speed by using the fact that you know the range of values in advance.

Common mistakes

One mistake is to use a list of tuples or a dictionary when you know the value range is small. Both work, but a frequency array is simpler and faster. The index is the value, so you do not need to search for it. A dictionary needs to look up the key each time. An array jumps straight to the right slot.

Another mistake is forgetting to initialize the array to the right size. If you know values range from 0 to 25, the array must have 26 slots. Slot 0 is for value 0, slot 25 is for value 25. Indexing off by one crashes the program or produces wrong answers.

A third mistake is using the wrong bounds. If digits are the values (0 through 9), your array has size 10, not 9. Count off: slot 0, slot 1, ... slot 9. That is ten slots. The rule is simple: size equals the range.

A fourth trap is forgetting to handle characters or values that fall outside the valid range. If you read a lowercase letter but your array only handles digits, or if you read an uppercase letter when you expect lowercase, the index calculation breaks. Always filter or convert your input to match the range your array covers.

When building a frequency array for characters, remember that uppercase and lowercase letters are different. 'A' and 'a' have different ASCII values. If the problem mixes cases, either treat them as distinct or convert all input to one case first.

When frequency arrays fit

A frequency array is a great choice when values fall into a known, narrow range. Digits are always 0 through 9. Letters are always a through z (or uppercase). Player IDs might be 1 to 1000. In each case, the range is fixed and small.

If the range is huge but the data is small, a frequency array wastes memory. A dictionary or a list of tuples is better. If you do not know the values in advance, you cannot use a frequency array.

Frequency counting is one pass, one update per value. Use it whenever the problem gives you a bounded range and you need to count.