Counting lists in Python

Why this matters

Many problems ask how often something happens. How many times does each digit appear in a list of phone numbers? Are two words made of the same letters? Which letter is the first one that appears only once? Each question is about counting. A counting list is the simplest tool for these problems, and it is fast: one pass over the data, and each count is found by direct lookup, with no searching.

The lessons before this one showed how to read and change items in a list. This lesson uses one idea on top of that. The value you are counting becomes the position in the list where its count is stored.

This lesson covers only the counting trick and its limits. Sorting the values to count them is covered in the sorting module. Counting with a dict is covered in the dictionary module, and this lesson shows it as the fallback for large values.

The idea: the value is the index

A list is a row of boxes. Each box has a number, and you find a box by its index, the position from zero.

Suppose you want to count the digits 0 to 9 in a list. Make a list with ten boxes, one for each digit. Box number 0 holds the count of zeros, box number 1 holds the count of ones, and so on. Each time you see a digit d, you add one to box number d.

Here is the rule in code:

count = [0] * 10
d = 7
count[d] += 1

The line count[d] += 1 means "add one to the box at position d". After the line runs, count[7] is one bigger than before.

A new list made with [0] * 10 starts with every box set to zero, so you do not need to set up the boxes yourself. The boxes start at zero, which is the right starting count.

Two words are used in this lesson. A count list is a list whose boxes hold counts. A key is the value being counted, such as a digit or a letter. The key is turned into an index, and the box at that index holds the count for the key.

First example: counting digits

Here is a short list of numbers, and a count list that counts how often each digit from 0 to 9 appears.

Output:

0 appears 0 times
1 appears 2 times
2 appears 1 times
3 appears 2 times
4 appears 1 times
5 appears 3 times
6 appears 1 times
7 appears 0 times
8 appears 0 times
9 appears 1 times

Walk through the first loop by hand. The first number is 3, so count[3] goes from 0 to 1. The second number is 1, so count[1] goes from 0 to 1. The third number is 4, so count[4] becomes 1. The fourth number is 1 again, so count[1] goes from 1 to 2. The loop keeps going until every number is used. At the end, box 1 holds 2 because the number 1 appears twice in the list.

The second loop does not count anything. It reads the boxes in order and prints them. This is the second common step in a counting problem: count in one pass, then read the answer in another.

Notice what the program did not do. It did not compare each digit with every other digit, and it did not search for the digit in a list. Each number caused one addition to one box. For a list of n numbers, the counting loop does n additions.

The f-string f"{digit} appears {count[digit]} times" puts the values of digit and count[digit] into the text in place of the braces.

Second example: counting letters in a string

Digits are easy because the values 0 to 9 are already numbers. Letters are not numbers, so a letter needs a conversion before it can be an index.

Python stores each character as a code point, which is a number. The function ord gives the number of a character, so ord("a") is 97 and ord("b") is 98. The function chr goes the other way, from a number to a character. A character code minus another character code gives the difference between their numbers. So ord("c") - ord("a") is 2. This means the letters a to z can be turned into the indexes 0 to 25 by subtracting ord("a").

Output:

a: 4
b: 2
d: 1
e: 1
n: 2
r: 1

There are three steps in the counting loop. The loop for ch in text gives each character in turn. The if line skips anything that is not a lowercase letter, such as the space in the middle. The Python comparison "a" <= ch <= "z" checks that the character falls between the two letters in the code order. The line count[ord(ch) - ord("a")] += 1 converts the letter to its index and adds one to that box.

The output loop goes the other way. It turns an index back into a letter. The expression ord('a') + k adds the index to the code of a, and chr turns the result back into a letter. Without chr, Python would print the number 97 instead of the letter a.

The count list has 26 boxes because there are 26 lowercase letters. If you also wanted capital letters, you would use 52 boxes, or convert each letter to lowercase first with ch.lower(). Keep the conversion in mind, because the same subtraction is the main source of mistakes in this lesson.

Third example: checking for anagrams with one list

Two words are anagrams if they use the same letters the same number of times. listen and silent are anagrams. rat and car are not.

You could sort both words and compare them, but that is a sorting lesson. Here you can do it with one count list and no sorting. The trick is to add one for each letter in the first word and subtract one for each letter in the second word. If the words are anagrams, every box ends at zero.

Output:

True
False

The function zip(a, b) pairs up the letters of the two words, one from each word at each position. Each pair x, y reads one letter from a and one letter from b. If the letter in a is l and the letter in b is s, the box for l goes up by one and the box for s goes down by one. A box that goes up and then comes back down cancels out. A box that never comes back to zero shows that one word has a letter the other word does not have in the same amount.

The early check on the length is needed. Without it, two words of different lengths could still leave every box at zero. For example, aa and a give one matching pair, so every box ends at zero and the function would return True. The length check makes the rule correct. Also, zip stops at the shorter of its two inputs, so the check keeps the loop from silently skipping letters.

The last line all(d == 0 for d in diff) is true only when every box is zero. The function all takes a sequence of true-or-false values and returns true when every one is true.

This version assumes the strings use only lowercase letters. If a space or a capital letter appears, ord(x) - ord("a") can give an index outside the list, and Python stops the program with an error. Some capital letters give a negative index instead, which counts into the wrong box without an error. A later section shows that error.

Fourth example: first character that appears once

Counting does not always end with the counts. Sometimes the counts are used to make a second decision. A common question is: what is the position of the first character that appears exactly once?

You need two passes. The first pass fills the count list. The second pass walks the string from the start and returns the first position where the count is one.

Output:

1
-1

In swiss, the letter s appears three times, and the letter w appears once at position 1. The second pass checks position 0 first. The letter s has a count of 3, so it is skipped. Position 1 has the letter w, which has a count of 1, so the function returns 1.

In aabb every letter appears twice, so no position has a count of one, and the function returns -1. The value -1 is a common way to say "not found" when the answer would normally be an index. It is not a position in the string, so the caller can check for it.

The function enumerate(s) gives the position i and the character ch together on each pass, so the second loop does not need a separate counter.

Notice that the second pass does not count again. It reads the same list that the first pass filled. Reusing the finished count list is the main benefit of this technique. Once the counts exist, you can ask many questions about them with simple lookups.

When the values are large

Everything so far depended on one condition. The values must be small enough to fit in a list. The digits 0 to 9 need ten boxes. The lowercase letters need 26 boxes. A value like 12 needs 13 boxes, which is still cheap. A value like one billion needs one billion boxes, and that is a problem.

Four things can go wrong with the values or their size, and the errors are different in each case. One of them is quiet, so read this part carefully.

A value outside the list

If the value is bigger than the last index, Python stops the program. Here the list has ten boxes, with indexes 0 to 9, and the code tries to count the value 12.

count = [0] * 10
value = 12
count[value] += 1
print("after")

Output:

Traceback (most recent call last):
  File "main.py", line 3, in <module>
    count[value] += 1
    ~~~~~^^^^^^^
IndexError: list index out of range

The last line names the problem. IndexError means you used an index that is not inside the list. The message does not give the index or the length, so count the boxes yourself. The index was 12 and the list has 10 boxes. The word after is never printed, because the program stopped before that line.

A negative value that does not fail

A negative value is different. Python counts negative indexes from the end of the list, so count[-1] is the last box. A negative value does not stop the program. It quietly counts in the wrong box.

Output:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

The count for the value -1 went into box 9, the last box, and no error appeared. A count for the digit 9 and a count for the value -1 now share the same box. The result looks normal, so this kind of error is hard to see. Check the range of the values before you count them, or reject negative values on purpose.

A size that is too big to create

The second problem happens before any counting starts. If the largest value is one billion, the list needs one billion boxes. Each box in a Python list holds a reference (a stored pointer to the value), which takes 8 bytes on a typical 64-bit computer, so the list needs about 8 GB of memory. This program is not run here, because it would take most of the memory on a typical computer.

On a computer with less free memory, Python stops with a MemoryError, or the system slows down while it looks for space. The line that fails is the line that creates the list, not the line that counts. The memory needed grows with the largest value, not with the number of values you count.

A size that is negative

The third case is a size that comes out negative because of a calculation. In many languages, new int[n] with a negative n stops the program with an error. Python does not. A list multiplied by a negative number is simply empty:

Output:

0

Here the list is empty, and every later count raises an IndexError, so the error shows up away from its cause. Check that the size is zero or more before creating the list, especially when the size comes from input.

The fix: a dict for large or sparse values

When the values are large but there are only a few of them, a counting list wastes most of its boxes. A list of ten values that range up to one billion needs one billion boxes, and only ten of them would ever hold a count. A dict solves this. A dict stores a key and a value as a pair, and it only uses memory for the keys that were actually added.

Output:

3
2
1
None
3

The method count.get(v, 0) returns the current count for v, or 0 if v is not in the dict yet. The line adds one and stores the result. The value 42 was never added, so count.get(42) returns None, which means no value is stored for that key. The length of the dict is 3, because there are three distinct values.

The standard library also has collections.Counter, a dict made for this job. Counter(values) counts the list in one call. A Counter returns 0 for a missing key when you write counts[key], but counts.get(key) returns None, as with a dict. This lesson uses a plain dict so the missing case is visible.

The dict is slower per step than a list, because it has to find the key first. For most values this difference is small. The list is still the better choice when the values are known to be small, because it is simpler and faster.

Another option is to sort a copy of the values and count runs of equal numbers next to each other. This uses little extra memory, but it needs sorting, which is covered in the sorting module.

Choosing between them

A short rule helps. Use a count list when the values are whole numbers from a known small range, such as digits, letters, dice rolls, or ages from 0 to 120. Use a dict when the values are large, unknown, or spread out with big gaps. Ask this question before you write the code: what is the largest value that can appear, and how many boxes would that need?

Common mistakes

Off by one in the size. If the values can be 0 up to 9, the list needs 10 boxes. Writing [0] * 9 gives boxes 0 to 8, and the value 9 causes IndexError: list index out of range. The number of boxes is one more than the largest value.

Forgetting the subtraction. A letter such as d has the code 100. Using it directly as an index gives count[100], which is far outside a 26-box list. Subtract ord("a") first, so that d becomes index 3.

Output:

100
3

Using capital letters with lowercase arithmetic. The code for A is 65, and the code for a is 97. Subtracting ord("a") from A gives -32, which is outside a 26-box list, so Python raises IndexError. A capital letter such as Z, whose code is 90, gives -7, a valid negative index, so it counts into box 19 without an error, as the negative index example showed. Convert the text to lowercase first with text.lower().

Counting twice. After the first pass, the counts are final. A beginner sometimes counts again in the second pass, which doubles every count. Count once, then only read.

Reusing counts from an earlier call. If the count list is a variable outside the function, or the same list is passed to two calls, the second call adds to the first call's counts. Create a new list inside each call, as the examples above do.

Assuming the size is safe. A size that comes from user input can be huge, negative, or zero. Check it before the list is created. A negative size does not raise an error in Python, so the check has to be written by hand.

Practice

Try each one before you read the answer. Save each program as main.py and run it with python3 main.py.

1. Grades are stored as the characters A, B, C, D, E and F in a list called grades. Write code that counts how many times each grade appears, using a count list of length 6. Test it with the grades ['A', 'C', 'B', 'A', 'F', 'A'].

Show the answer

Use the index ord(grade) - ord("A"), so A goes to box 0 and F goes to box 5.

Output:

[3, 1, 1, 0, 0, 1]

Three A grades, one B, one C, zero D, zero E, and one F.

2. You have a list scores where every score is between 0 and 100. Write a function that returns the score that appears most often. If two scores tie, return the smaller one. Test it with [70, 85, 70, 92, 85, 85, 60].

Show the answer

Build a count list of length 101. Then scan the boxes from 0 upward and keep the first box with the highest count. Scanning upward means a tie keeps the smaller score, because the strict > comparison does not replace an earlier box.

Output:

85

85 appears three times and 70 appears twice, so the answer is 85.

3. Predict what this program prints, then run it to check.

count = [0] * 5
values = [1, 3, 3, 4, 5]
for v in values:
    count[v] += 1
print(count[3])

Show the answer

The program does not print a count. The value 5 is not a valid index for a list of length 5, because the valid indexes are 0 to 4. Python stops with IndexError: list index out of range, and the line print(count[3]) never runs. The fix is to make the list length 6, because the largest value is 5.

4. Write a function count_vowels(s) that returns how many of the letters a, e, i, o and u appear in s. Use a count list of length 26 and then add up the boxes for the five vowels. Test it with "education", which has five vowels.

Show the answer

Output:

5

For "education" the answer is 5. The letters are e, d, u, c, a, t, i, o, n, so the vowels are e, u, a, i, o. The sum function adds the five boxes, one for each vowel letter in the string "aeiou".

5. A survey stores each person's age in a list ages. Ages can be from 0 to 120. Write a function that counts how many people are each age, using a count list. Then explain in one sentence why a count list of 2,000,000,000 boxes would be a poor choice if the ages were replaced by user IDs up to 2,000,000,000.

Show the answer

Output:

2

The age list needs only 121 boxes. A count list for user IDs up to 2,000,000,000 would need about 16 GB, since each box holds an 8-byte reference, and most of those boxes would never hold a count. A dict from ID to count would store only the IDs that actually appear.

Summary

• A count list uses the value itself as the index, and each box stores how many times that value appeared.
• A new list made with [0] * n starts every box at zero, so no setup loop is needed.
• Letters become indexes by subtracting ord("a"), which turns a into 0 and z into 25.
• A counting pass followed by a reading pass answers many questions, such as the first character that appears once.
• Large values cause errors: an index outside the list raises IndexError, a negative index counts in the wrong box without an error, and a list that is too big uses too much memory.
• For large or spread-out values, a dict stores only the values that actually appear.