Boolean seen lists in Python

Why this lesson matters

Many programs need to answer one question again and again: have I already seen this value? A list of student ids needs a duplicate check. A game needs to know which cards are already dealt. A test needs to know which numbers it has used so far.

Python has a ready-made answer for this, the set type. A set is a collection that stores each value once and answers "is this value in the set?" quickly. It works for any values that Python can store in a set, including text and very large numbers. Sometimes, though, the values are whole numbers in a small known range, such as marks from 0 to 100 or card numbers from 1 to 52. For that case a plain list of True and False flags is simpler and uses less memory.

This lesson shows how to use a list of flags as a seen-set, a record of which values have appeared. It also shows how to clear the list cheaply between tests, which matters when one program runs many test cases.

The idea: the index is the value

A bool holds one of two values, True or False. A list of these is a flag list. When you create one with [False] * 101, Python gives you 101 positions, indexes 0 to 100, and sets every one of them to False. You do not need to fill it yourself.

Use the value as the index. If the value 7 has been seen, then seen[7] is True. If it has not, seen[7] is still False. Checking a value takes one step: look at its index.

Take the marks 3, 1, 4, 1, 5. The marks are all between 0 and 5, so the list needs 6 positions. Here is the list after each mark is added.

values seen so far    index:  0      1      2      3      4      5
start                        False  False  False  False  False  False
after 3                      False  False  False  True   False  False
after 1                      False  True   False  True   False  False
after 4                      False  True   False  True   True   False
next mark is 1               seen[1] is already True, so 1 is a repeat

The repeat is found on the fourth mark. The code only needs to read one position to know it.

The method has one hard requirement. The range of possible values must be known before you start, and the list must be big enough to hold every value in that range. The list length is the largest value plus one, because indexes start at 0. If the largest possible value is 100, the list needs 101 positions.

Worked example 1: a duplicate check

Here is the simplest use. The function returns True if any value appears twice. It assumes every value is between 0 and max_value.

Output:

True
False
False

The first line of the function creates the list. The loop for v in values reads each value in turn. The check if seen[v] reads the flag at that value's index. If the flag is already True, the function stops early and returns True. If not, the function sets the flag and moves on.

The first line of output is has_duplicate([3, 1, 4, 1, 5], 5), which is True. The second is has_duplicate([3, 1, 4, 0, 5], 5), which is False. The third is an empty list, which has no repeats, so False.

Worked example 2: which numbers are missing

The next example uses a slightly different list. Suppose a list holds n values, and each value is between 1 and n. A value might appear twice, so some numbers from 1 to n may be absent. The function returns the absent numbers in increasing order.

Output:

[2]
[]

The first result is [2], because the input [4, 3, 3, 1] has values 1, 3 and 4 and is missing 2. The second is empty, because [1, 2, 3] contains every number from 1 to 3.

The list comprehension [i for i in range(1, n + 1) if not seen[i]] does the second pass in one line. It keeps each i whose flag is False. The word not flips the flag, so not seen[i] is True when the number is missing. Python lists grow, so the result list needs no size count before it is built. In a language with fixed-size arrays, the program would count the missing numbers first to size the result, and the comprehension avoids that step.

Worked example 3: the first missing positive

This example is harder because the input can contain values that are useless for the check, such as negative numbers, zero, and values bigger than the list. The task is to find the smallest positive whole number that is not in the list.

The trick is to ignore every value outside the range 1 to n. A value outside that range can never be the answer. The answer is always in the range 1 to n + 1, because a list of n values can cover at most n positive numbers. If every number from 1 to n is present, the answer is n + 1.

Output:

2
3
1
1

The chained comparison 1 <= v <= n means "v is at least 1 and at most n". Python reads it as one test, so the check needs no and.

Before you write code for a problem like this, decide which values the list must hold, then size it from the top of that range. Here the top of the range is n, so the list has n + 1 slots.

The input [3, 4, -1, 1] has 1 and 3 and 4 in range, so 2 is the first gap. The input [1, 2, 0] has 1 and 2, so the first gap is 3. The input [7, 8, 9, 11, 12] has no 1, so the answer is 1. The empty list has no values, so the answer is 1.

Resetting between tests

A program that runs many tests will call the same function many times. Each call must start with an empty seen-set. There are three ways to make that happen.

The first way is to create a new list for each test. This is the simplest, and has_duplicate above does it. The cost is that Python must create and fill a new list each time, and the cost grows with the size of the range.

The second way is to clear the existing list with a slice assignment, seen[:] = [False] * len(seen) ([:] means the whole list). It sets every slot back to False and keeps the same list object. It is quick to write. Its cost still grows with the size of the range, because every slot is visited. If the range is a million values and the tests are small, most of the work is clearing slots that were never used.

The third way is a stamp list. Instead of a flag, each slot holds an int that records the number of the test which last marked it. A reset then only changes one number, the current test number. Every slot that holds an old number now looks unseen, and nothing is visited. The class below does this.

Output:

False
False
True

The first call sees 3 for the first time, so it returns False. After reset, the value 3 is new again, so the second call returns False. The third call in the same test sees 3 again, so it returns True.

The starting value of current is 1, not 0. The list [0] * size starts every slot at 0. If current also started at 0, every value would look already seen before the first call. Starting at 1 keeps the empty slots distinct from the current test.

The stamp method has one limit. Python integers have no size limit, so the counter never wraps back to an old value, and the stamps never collide. The counter is a single int, so it stays small even after millions of resets.

Choosing between a list and a set

The list is not always the right tool. The choice depends on the range of the values and on what the values are.

Use a flag list when the values are whole numbers in a small range that you know in advance. Marks from 0 to 100 need 101 slots, which is trivial. Each check is a single index read, and the code is short.

Use a set when the values are text, when they are spread over a huge range, or when the range is not known. A set stores only the values that were added, so a set of five large ids takes space for five values. A flag list over the range 0 to 2,000,000,000 would need 2,000,000,001 slots. A list stores a reference to each slot, which takes 8 bytes on a typical 64-bit Python, so that list would need about 16 GB, even if only five values were ever marked. A bytearray stores one byte per slot, and it would need about 2 GB, which is still far more than a set of five values.

The sizes are easy to check. A list of 1000 flags takes about 8 KB on a typical 64-bit Python, and a bytearray of 1000 bytes takes about 1 KB. A set of three numbers takes a few hundred bytes. The exact figures depend on the Python version and the machine, so treat them as rough.

Both choices give the same answers. The difference is in the memory they use and in how much the code must know about the values before it runs.

Common mistakes

Forgetting to mark the value

This is the most common error. The code checks the flag but never sets it, so no duplicate is ever found. The code below has the line that sets the flag removed.

Output:

False

The answer is wrong, because the first 1 is never recorded, so the second 1 looks new. The fix is to add seen[v] = True after the check, as in the first worked example.

Off by one in the list size

The list needs one slot for each value from 0 to the maximum. If the maximum is 5, the list needs 6 slots, so [False] * (max_value + 1) is correct. Writing [False] * max_value leaves no slot for the maximum. Here is what Python prints when the code writes to index 5 of a 5-slot list:

seen = [False] * 5
seen[5] = True

Traceback (most recent call last):
  File "main.py", line 2, in <module>
    seen[5] = True
    ~~~~^^^
IndexError: list assignment index out of range

The file path on the File line depends on where you save the file, so it can differ on your machine. The message says the write failed at an index that the list does not have. The list has 5 slots, so the valid indexes are 0 to 4. The code asked for index 5, which is one too far.

Values outside the known range

If a value is bigger than the list, the code fails with an IndexError, Python's error for an index the list does not have. A negative value is worse, because Python does not fail on it. A negative index counts from the end of the list, so the value -1 marks the last slot and no error appears.

Output:

after -1: [False, False, False, False, False, True]

The value -1 marked slot 5, which belongs to the value 5. Any later check for 5 would report a repeat that never happened. When the input can contain such values, check the range first, as the first-missing-positive example does. Skip the value, or report it as an error.

Sharing one seen-set between tests without a reset

A flag left over from one test makes the next test report a duplicate that never happened. In this example the first call marks 2, and the second call, which has values 2 and 3, sees 2 as already seen.

Output:

False
True

The second call returns True. The value 2 is a leftover from the first call, and there is no repeat in [2, 3]. Clear the list with shared[:] = [False] * len(shared) or use a stamp list before each test.

Practice

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

Exercise 1

Write a function is_permutation that takes a list of integers and returns True when the values are exactly the numbers 1 to n, each appearing once, where n is the list length. For [2, 1, 3] it should return True. For [1, 1, 3] it should return False, because 2 is missing and 1 is repeated.

Show the answer

Output:

True
False

The function returns False at the first value out of range or repeated. If the loop finishes, all n values are different and lie in 1 to n, so every number in that range appears exactly once. The range check comes first, so a value of -1 is never used as an index.

Exercise 2

Using the flag idea from this lesson, write a function that counts how many different values are in a list. Values are between 0 and 100. For [5, 5, 7] it should return 2.

Show the answer

Output:

2

Running this on [5, 5, 7] gives 2, because two slots are True. Python treats True as the number 1 in a sum, so sum(seen) gives the same count in a shorter line. For values that are not in a small range, len(set(values)) counts the distinct values without any flag list.

Exercise 3

A test program uses a StampSeen object of size 10. It runs these calls in order: seen_before(3), reset(), seen_before(3), seen_before(3), reset(), seen_before(3). Predict each printed value.

Show the answer

The values are False, False, True, False. The first call is new, so False. After the reset, the second call is new again, so False. The third call sees 3 in the same test, so True. After the second reset, the stamp in slot 3 is from an old test, so the last call is False.

Exercise 4

A test harness runs 50,000 small tests. Each test uses values from 0 to 1,000,000 but only marks about 10 of them. Which reset method is the better choice, a new list per test, a slice reset per test, or a stamp list, and why?

Show the answer

The stamp list is the best choice. A reset just increments one number, so the cost does not depend on the range of 1,000,000. A new list per test creates and fills a million slots 50,000 times. A slice reset also visits a million slots on each reset. The stamp list uses the same memory as a flag list, since both hold one 8-byte reference per slot, about 8 MB for a million slots on a typical 64-bit Python. The stamp list is the right trade when resets are frequent.

Exercise 5

A student writes this function. It returns True for [1, 2], which has no repeat. Find the mistake and fix it.

def has_repeat(values):
    seen = [False] * 5
    for v in values:
        seen[v] = True
        if seen[v]:
            return True
    return False
 
print(has_repeat([1, 2]))

Show the answer

The flag is set before it is checked. So the check always sees True for the value just read, and the function returns True on the first value of any non-empty list. The check must come before the flag is set:

Output:

True
False

With the fix, [4, 2, 4] returns True and [1, 2] returns False.

Summary

• A flag list works as a seen-set when the values fall in a known range. The value is the index, and True means the value was seen.
• Check the flag first, then set it. Setting it before the check hides every repeat.
• Size the list as the largest possible value plus one, because indexes start at 0.
• Values outside the known range cause an IndexError when they are too big, and a negative value silently marks a slot from the end. Check the range first when the input is not trusted.
• A reset by a slice assignment costs time proportional to the range. A stamp list costs one increment per reset and uses the same memory as a flag list.