Longest consecutive sequence with a hash set

Why this matters

Many questions ask for a run inside a list of numbers. A run is a block of values where each one is exactly one more than the one before. A calendar app might ask for the longest streak of days with a login. A sensor log might ask for the longest stretch of readings that went up by one each time. This lesson solves that problem for numbers in any order, and it solves it without sorting first.

The simple way is to sort the list and count along it. Sorting costs about n log n steps for n numbers, which is fine for most programs. The method in this lesson does the job with a hash set. A hash set is a container that stores values with no duplicates and checks whether a value is present in about the same time for any size. In C++ it is unordered_set, from the earlier lessons in this module. Each check takes about one step on average, so the whole job takes about n steps on average. Computer scientists write that as O(n), which means the work grows in step with the number of values.

The word "average" matters. A hash set finds a value by computing a number from it and looking in one bucket, a small slot in a table. Most buckets hold few values, so the check is fast. In a bad case where many values land in one bucket, a check becomes slow. The earlier lessons on hashing cover that case. This lesson assumes the usual fast case, which is what the standard library delivers for integer keys.

The key idea is to avoid repeated work. The first version of this method walks upward from every value, and the same numbers get walked many times. The fix is to walk only from the start of each run.

What counts as a run

A run is a set of values that form an unbroken block of integers. The values 3, 4 and 5 form a run of length 3. The order in the input does not matter. The list 5, 3, 4 also contains that run.

Take this list:

100 4 200 1 3 2

The values 1, 2, 3 and 4 form a run of length 4. The value 100 has no neighbour and forms a run of length 1. The value 200 also forms a run of length 1. The answer is 4.

Duplicates do not make a run longer. The list 5, 5, 5 has only one distinct value, 5, so its longest run is 1.

The slow way first

The simplest idea is this. For each value x, count how far the run goes upward from x. Keep the best count. Here is that method with a counter for the number of steps it takes.

Take the input 1 to 1000, written in order, so there are 1,000 values. Starting from 1, the walk goes through 999 more values. Starting from 2, it goes through 998. Starting from 3, it goes through 997. The walks add up to 999 plus 998 plus and so on down to 0. That sum is 499,500 steps for 1,000 values. The number of steps grows with the square of the input size, so doubling the input makes the work about four times as large.

The waste is clear in that example. The walk from 1 already covered 2 through 1000, and the walks from 2, 3 and the rest covered the same values again. The fix is to skip every value that is not the start of its run.

The main idea: start only at the start of a run

A value x is the start of its run when x - 1 is not in the set. If x - 1 is in the set, then x sits inside a longer run that begins lower down, and that run will be walked from its own start. So the program skips every value where x - 1 is present.

For each start, the program walks upward while the next value is present. It counts the steps. Then it keeps the best count.

Take the input 100 4 200 1 3 2 again. The set holds 1, 2, 3, 4, 100 and 200. Here is what the program does with each value:

• 100: 99 is not in the set, so 100 is a start. The walk checks 101, which is not present. The run has length 1.
• 4: 3 is in the set, so 4 is skipped.
• 200: 199 is not in the set, so 200 is a start. The walk checks 201, which is not present. The run has length 1.
• 1: 0 is not in the set, so 1 is a start. The walk checks 2, 3, 4 and finds each one, then checks 5 and does not find it. The run has length 4.
• 3 and 2: both have a value below them in the set, so both are skipped.

The answer is 4.

Each value is walked by at most one start. A walk starts at a value with no predecessor and goes upward through the values of its run. No other walk can pass through those values, because every value inside a run after its first one has a predecessor in the set. So the walks never overlap, and the total work is about the number of values, plus one failed check per walk.

A short example by hand

Take the list 3, 1, 2, 9, 8. The distinct values are the same five numbers, so the set holds them all.

The naive walk starts at each value and counts upward. From 1 it finds 2 and 3, then stops at 4, which is absent. That is 2 steps and a run of 3. From 2 it finds 3 and stops, which is 1 step. From 3 it stops at once, with 0 steps. From 8 it finds 9 and stops at 10, which is 1 step. From 9 it stops at once. The total is 4 steps, and the answer is 3.

The smart method starts only where x - 1 is absent. Here 1 and 8 are the only starts, because 2, 3 and 9 each have a smaller neighbour in the set. The check for x - 1 runs once for each of the 5 values, which is 5 lookups. The walk from 1 makes 3 lookups, for 2, 3 and 4. The walk from 8 makes 2 lookups, for 9 and 10. The total is 10 lookups, and the answer is again 3.

For five values the difference is small. The gap widens as the input grows, as the second example below shows.

First example: the algorithm with a counter

The program below uses the method. It counts every call to the set, so you can see the work. The lambda has is a small function written inside longestRun. It asks the set whether a value is present, and it adds one to the counter each time.

The output is:

answer 4, lookups 12
answer 5, lookups 16
answer 0, lookups 0
answer 1, lookups 2

The first line is the example worked through above. Its 12 lookups split into 6 checks of x - 1, one for each distinct value, plus 6 more: one check of 101, one of 201, and four in the walk from 1. The second input is harder. The values are -2, -1, 0, 1, 2, 5, 7, 9 once the duplicate 2 is removed. The run -2 to 2 has length 5. Each of the 8 distinct values gets one check of x - 1, and the walk from -2 makes 5 checks. The other three starts each make one check. That gives 16 lookups.

The empty list gives 0, because no value is ever a start and best stays at 0. The list 5, 5, 5 gives 1. The set holds one value, which is the start of its run, and the walk checks 6 and finds nothing.

Negative numbers need no special handling. The walk goes upward from -2 in the same way as from 1. The program uses long long for the values. A value near the largest int plus the walk length can go past the limit of int, and overflow of a signed int is undefined behaviour in C++. The wider type avoids that for ordinary inputs.

Second example: the cost in numbers

The next program runs two methods on the input 1 to 1000. The first is the naive walk from every value. The second is the method above. It prints the answer and the work each method did.

The output is:

naive answer 1000, steps 499500
smart answer 1000, lookups 2000

Both methods give the same answer, 1000. The naive walk took 499,500 steps. The smart method made 2,000 lookups: one check of x - 1 for each of the 1,000 values, and one walk from 1 that made 1,000 checks, for the values 2 to 1,001. The gap grows with the input. For ten times as many values, the naive count grows about a hundredfold, and the smart count grows tenfold.

Third example: checking the method against sorting

A new method needs a test against a method you already trust. Sorting is slower, but simple. The program below builds random lists of small integers, including negative values and duplicates. For each list it computes the answer two ways and counts the cases where they disagree.

The sorted method sorts the values, removes duplicates with unique and erase, and then counts how many values in a row are one more than the one before. mt19937 is a random number generator, and uniform_int_distribution picks numbers from a range with each value equally likely. The random generator uses a fixed seed, so the same numbers come out on every run.

The output is:

random check disagreements: 0

A result of 0 is good evidence, not proof. The test covers 2,000 lists, all with values between -50 and 50. Edge cases such as very large values are not in the test, so a test like this is a starting point and not a guarantee.

Common mistakes

Walking from every value. Leaving out the if (has(x - 1)) continue; line turns the method into the naive walk. The answer is still correct, but the work grows with the square of the input. For the input 1 to 1000, the naive walk took 499,500 steps, against 2,000 lookups for the correct method.

Checking membership by searching a vector. A beginner may keep the values in a vector and call std::find for each check. That works, but find looks at the list one value at a time. Each check then takes as long as the list is long, and the whole method slides back toward the slow walk, with work that grows with the square of the input. The set exists so that each check is quick, so store the values in an unordered_set.

Using contains with an old compiler setting. The contains method on unordered_set was added in C++20. Compiling the same program with -std=c++17 fails with an error like this:

error: 'class std::unordered_set<long long int>' has no member named 'contains'

Either compile with -std=c++20, or use find, which works in C++17. The seventh exercise below shows the find version.

Forgetting the header. Without #include <unordered_set>, GCC reports that the name does not exist:

error: 'unordered_set' was not declared in this scope

Include the header that declares the container you use.

Counting duplicates in the answer. The answer is the length of a run of distinct values. For the list 5, 5, 5, the answer is 1, not 3. The set removes the duplicates, so the walk never sees them twice. A common wrong fix is to count the list length instead of the run length.

Using int for the values and the walk. When a value is near the largest int, the expression x + length can overflow. Signed overflow is undefined behaviour in C++. The examples use long long to avoid this for ordinary inputs.

Forgetting the empty list. The empty input must return 0. The code does this because best starts at 0 and the loop never runs. If you change the starting value of best to 1, the empty list will return 1, which is wrong.

Practice

Exercise 1. What is the longest run in the list 1, 2, 0, 1?

Show the answer

The distinct values are 0, 1 and 2. They form one run of length 3. The duplicate 1 does not add to the length, so the answer is 3.

Exercise 2. In the list 10, 12, 11, 14, which value is the start of its run, and what is the answer?

Show the answer

The distinct values are 10, 11, 12 and 14. The value 10 is a start, because 9 is not present. The values 11 and 12 are not starts. The value 14 is a start, because 13 is not present. The run from 10 has length 3, and the run at 14 has length 1. The answer is 3.

Exercise 3. Which values are starts in the list 9, 1, 4, 7, 3, 2, 10?

Show the answer

The distinct values are 1, 2, 3, 4, 7, 9 and 10. The value 1 is a start, because 0 is not present. The value 7 is a start, because 6 is not present. The value 9 is a start, because 8 is not present. The value 4 is not a start, because 3 is present. The values 2, 3 and 10 are not starts either.

Exercise 4. For the list 1, 2, 3, how many lookups does the program in the first example make, and what is the answer?

Show the answer

The answer is 3. The program makes 3 checks of x - 1, one for each value, with 0, 1 and 2 as the checks. Only the value 1 is a start, so it walks upward: it checks 2 and 3, which are present, and 4, which is not. That walk adds 3 more lookups, for a total of 6.

Exercise 5. In the list -3, -2, -1, 0, what is the longest run?

Show the answer

The four values are consecutive, so the run has length 4. The start is -3, because -4 is not present. The answer is 4.

Exercise 6. Which line of the method makes the walk skip values that are not the start of a run?

Show the answer

The line is if (seen.contains(x - 1)) continue;. When x - 1 is in the set, x is not the start of its run, so the loop moves on to the next value. The continue keyword jumps to the next pass of the loop.

Exercise 7. Rewrite the has lambda so the program compiles with -std=c++17.

Show the answer

Replace the lambda body with a call to find:

auto has = [&](long long v) {
    lookups++;
    return seen.find(v) != seen.end();
};

The find method returns an iterator. If the value is not present, the iterator equals seen.end(), so the comparison tells the program whether the value is there.

Summary

• A run is a block of distinct integers where each value is one more than the one before, in any input order.
• Walking upward from every value repeats work, and for a run of 1,000 values the naive walk took 499,500 steps.
• A value is a start of its run when the value one less is not in the set. Walk only from starts.
• Each value is walked at most once, so the work is about the number of values, with an average constant time check for each.
• Remove duplicates by storing the values in a set, and make sure the answer is the length of a run, not the length of the list.
• Test a new method against a simpler method you trust, such as sorting, on many random inputs.