Longest consecutive sequence with a Python set

Why this matters

Many programs need to know how long a streak is. A fitness app counts the most days in a row a user logged a workout. A monitoring tool looks for the longest stretch of time without an error. A game checks the longest chain of matching tiles. Each of these asks the same thing: given a pile of numbers, find the longest run where each value is one more than the value before it.

The obvious way to solve this is to sort the numbers and scan them once. That works, and it is a good first answer. This lesson shows a second way that avoids sorting. It uses a set, which answers "is this value present?" in about one step. With that tool, the whole job takes one pass over the numbers plus one walk through each run. You will see why each number is looked at only a few times, and why one small check decides whether the program is fast or very slow.

This lesson builds on the idea of a hash table from the earlier lessons in this module. If you have not used a set before, read its description in the next section first.

The problem: longest run of consecutive numbers

A consecutive run is a list of whole numbers where each number is exactly one more than the one before it. The numbers 1, 2, 3, 4 are a consecutive run of length 4. The numbers 1, 2, 4 are not, because 3 is missing.

You get a list of integers in no particular order. Some values may repeat. Return the length of the longest consecutive run that the list contains. The numbers in the run do not have to be next to each other in the list.

Here is the first example, worked by hand. The list is 100, 4, 200, 1, 3, 2.

values:          100   4   200   1   3   2
runs found:      [100]   [4]  [200]  [1, 2, 3, 4]
longest run:     4   (the run 1, 2, 3, 4)

The values 1, 2, 3 and 4 are spread out in the list, but they form one run. The value 100 and the value 200 each stand alone. The answer is 4.

A first idea: sort, then scan

If the numbers are sorted, a run is easy to see. The values 1, 2, 3, 4 sit next to each other, and the code only needs to count how many times the next value is exactly one bigger. Put the numbers in a set first, so repeated values disappear, and then sort the set.

4
1

The function set(nums) removes duplicates, so 9, 9, 9 does not count as a run of three. The zip function pairs each value with the one after it. Each time the next value is exactly one more, run grows. Any other gap resets run to 1.

Sorting costs time. Python's sorted takes about n times log n steps for n numbers. For a million numbers that is much more work than one pass. The set approach avoids the sort.

The tool: a set for "is it there?"

A set stores values with no duplicates and no particular order. The main question you ask of a set is in. Given a number, x in numbers answers True or False. On average it takes about one step, no matter how many values the set holds. That is the same speed idea as the dict from earlier lessons: the set computes a slot for the value and checks that slot.

The set takes the values from the list. Repeated values are stored once, which removes the duplicates for free.

numbers = set(nums)

The values in the set are ordinary int objects, and the set keeps one copy of each. Lesson 3 covered what each int object costs in memory.

Now the question is how to use in to find runs without looking at every value in order.

The key idea: start counting only at the start of a run

Here is the trick. For each number n in the set, ask whether n - 1 is also in the set.

• If n - 1 is in the set, then n is in the middle or the end of a run. The run was (or will be) counted from its start, so skip n.
• If n - 1 is not in the set, then n is the first value of its run. Start counting from n. Check whether n + 1 is present, then n + 2, and so on, until a value is missing. The count at that point is the length of this run.

Go back to the example, 100, 4, 200, 1, 3, 2. The set holds the six values.

• 100: is 99 in the set? No. So 100 starts a run. Is 101 in the set? No. Run length 1.
• 4: is 3 in the set? Yes. So 4 is in the middle of a run. Skip it.
• 200: is 199 in the set? No. So 200 starts a run. Is 201 in the set? No. Run length 1.
• 1: is 0 in the set? No. So 1 starts a run. Is 2 in the set? Yes, count 2. Is 3 in the set? Yes, count 3. Is 4 in the set? Yes, count 4. Is 5 in the set? No, stop. Run length 4.
• 3 and 2: each has its predecessor in the set, so both are skipped.

The best run is 4. The code for this is short.

4
9
4
0
1
3
4

The variable length starts at 1 because n itself is in the run. Inside the while loop, n + length is the next value we need. When in returns False, the run has ended, and length is the number of values in it.

The loop for n in numbers visits the set in whatever order Python gives. The answer does not depend on that order, because the check "is n - 1 present?" gives the same result for each value wherever it appears in the loop.

Why this is fast: each number is walked over once

It might look like the while loop could be slow. If the list holds 1,000 values in one long run, the code might walk over them many times. It does not, and the reason is the check at the top of the loop.

A value is walked over only when it is the start of its run. Every other value is skipped in one step. So each run is walked exactly once, from its start to its end. Walking a run of length L takes L steps, and the sum of all the run lengths is at most the number of values. The total work is therefore about the number of values, plus a single check per value.

The step counts below come from a copy of the code that counts each move. The count is the number of values the outer loop looked at, plus the number of moves the while loop made. The from every lines use the version that starts a walk from every value, which the mistakes section explains.

example 1 with starts: (4, 9)
example 1 from every: (4, 12)
example 2 with starts: (9, 17)
example 2 from every: (9, 45)
1000 in a row with starts: (1000, 1999)
1000 in a row from every: (1000, 500500)

Each pair is (answer, steps). For the first example, the outer loop looks at 6 values. The walk from 1 makes 3 moves, to 2, 3 and 4. The total is 9. For the second example, the set has 9 distinct values, 0 through 8, all in one run, so the answer is 9. The outer loop visits 9 values and the walk from 0 makes 8 moves, for 17 steps in total.

The numbers in the last two lines are the point of the lesson. With the check, a run of 1,000 values costs 1,999 steps. Without it, the same run costs 500,500 steps.

Worked example two: a longer, unsorted list

Now a harder input with duplicates and a run in the middle. The list is 0, 3, 7, 2, 5, 8, 4, 6, 0, 1. The value 0 appears twice.

The set holds 0, 1, 2, 3, 4, 5, 6, 7, 8. The value 0 is stored once. Going through the set in whatever order Python gives:

• Any value n where n - 1 is in the set is skipped. That covers 1 through 8, because each has its predecessor present.
• 0 has no predecessor, since -1 is not in the set. It starts a run. It counts up through 1, 2, 3, 4, 5, 6, 7, 8, and stops at 9, which is missing. The length is 9.

The answer is 9. The order in which Python visits the set does not matter, as the section above explained.

Worked example three: negatives and repeats

Negative numbers need no special handling. The list -3, -2, -1, 0, 0, 5 contains the run -3, -2, -1, 0, which has length 4. The repeated 0 is stored once in the set, so it does not add to the count. The value 5 stands alone.

The inputs in the code above cover the cases you should test: a list in mixed order, a list with duplicates, negatives, an empty list, a list of one repeated value, a list where a repeat sits inside a run, and a list that is one run from start to end. Each result matches the answer you would get by hand.

Comparing the three approaches

Here is how the approaches compare for n values.

The set version uses more memory, because it stores every value. The sorted version stores a sorted copy of the values. Both use memory in proportion to n. The set version is the one that runs in about n steps, which is why it is the usual answer for this problem.

The word "about" carries weight here. A set looks up values in about one step on average, not in exactly one step every time. Under normal conditions the average holds, and the total work stays close to n.

Common mistakes

Starting a count from every value. If you remove the check if n - 1 in numbers: continue, the answer is still correct, but the work can grow too fast. Each value starts its own walk, so a run of length L gets walked L times. The 1,000-value example above shows the difference: 1,999 steps with the check, and 500,500 steps without it. The check is the one line that makes the solution linear.

Using a list instead of a set. A list also supports in, but it checks the items one by one from the start. Each check takes time that grows with the list. The code still returns the right answer, but every lookup becomes a scan. The set version gives the same answers much faster on long lists. Build the set once with set(nums), then use it for every check.

Putting an unhashable value in a set. A set holds only hashable values, meaning values with a hash number that never changes, and a list is not hashable. A list of pairs, such as [[1, 2], [2, 3]], cannot go into a set directly. Python raises an error that names the problem:

pairs = set([[1, 2], [2, 3]])

TypeError: cannot use 'list' as a set element (unhashable type: 'list')

Use tuples, such as set([(1, 2), (2, 3)]), when the items are small groups of values.

Removing values from the set while looping over it. Some people remove values as they visit them, to avoid counting twice. Changing a set while a for loop walks over it raises an error. The program below removes the odd numbers while it loops:

numbers = {100, 4, 200, 1, 3, 2}
for n in numbers:
    if n % 2 == 1:
        numbers.remove(n)

RuntimeError: Set changed size during iteration

The check n - 1 in numbers needs the set unchanged while you walk it, so keep it that way. If you do need to remove values, loop over list(numbers), which is a copy, or collect the values to remove in a second list and remove them after the loop.

Expecting an overflow at the edge of the range. In Java, an int wraps around when it passes its largest value, so the walk needs a long. Python integers do not wrap. They grow as large as the memory allows, so the walk works with no special type:

print((2**31 - 1) + 1)
print(longest_consecutive([2**31 - 1, -2**31]))

2147483648
1

The two values in the second line are not consecutive, so the answer is 1, which is correct. In Java the same input would wrap the arithmetic and report a false run of 2.

Counting repeats as part of the run. A repeated value does not make the run longer. The list 9, 9, 9 has one distinct value, so its answer is 1. Count the distinct values in the set, not the items in the list.

Practice

Each exercise has an answer below it. Work each one on paper first.

1. Find the longest consecutive run in 1, 2, 0, 1. Name the values in the run.

Show the answer

The longest run is 3. The values are 0, 1 and 2. The repeated 1 does not change the answer.

2. Find the longest consecutive run in 10, 5, 6, 7, 20. Which values are walked over, and which are skipped?

Show the answer

The answer is 3. The value 5 has no predecessor, so it starts a run and the walk visits 6 and 7. The value 6 and the value 7 are skipped, because each has its predecessor in the set. The values 10 and 20 each start a run of length 1.

3. Why does the check n - 1 in numbers make the solution fast on a run of 1,000 values?

Show the answer

Without the check, every value in the run starts its own walk, so the total work is about 500,500 steps for 1,000 values. With the check, only the first value walks the run, so the total is about 2,000 steps, which is the 1,000 outer visits plus 999 moves.

4. The list [2**31 - 1, -2**31] is passed to a solution that wraps integers at 32 bits, like Java's int. What does it print, and what should it print?

Show the answer

A wrapping solution prints 2, because the largest 32-bit value plus 1 wraps to the smallest one, which is in the set. The correct answer is 1, because the two values are not consecutive. Python prints 1 without any special handling.

5. How many steps does with_steps count for the list 1, 2, 3, 4 when it starts a walk from every value, with no check? Count the outer loop visits and the walk moves.

Show the answer

The outer loop visits 4 values. The walks make 3 moves from 1, 2 from 2, 1 from 3 and 0 from 4, which is 6 moves. The total is 10 steps, and the program prints (4, 10).

Summary

• A set answers "is this value present?" in about one step on average, so you can search for runs without sorting.
• For each value n, check whether n - 1 is in the set. Only start a count when it is not, which means n is the first value of its run.
• Each run is walked once from its start, so the total work is about the number of values, not the square of it.
• Do not change a set while looping over it. Loop over a copy when you need to change it.
• Python integers do not overflow, so the walk needs no special type.