LESSON 245 OF 347 · HASH TABLE

Longest Consecutive Sequence in C#: O(n) with a HashSet

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example 1:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
             Therefore its length is 4.

Example 2:

Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
             Therefore its length is 4.
	     Note that we count each value once, even tho values 0, 1 and 2 appear 2 times each in nums

Note:

Your algorithm should run in O(n) time and use O(n) extra space.

STEP 1 OF 8

Guided

Ctrl + Enter to check

C# · HASH TABLE

Longest Consecutive Sequence in C#, explained

Problem overview

The method LongestConsecutive receives an unsorted int[] nums and returns the length of the longest run of consecutive integers that can be formed from its values. The run does not have to appear in order in the array, and a repeated value counts once.

For [100, 4, 200, 1, 3, 2] the values 1, 2, 3, 4 form a run of length 4, so the answer is 4. In the second example, [0, 2, 0, 1, 2, 3, 1], the values 0, 1, 2, 3 also give 4, even though 0, 1 and 2 each appear twice.

The statement requires O(n) time and O(n) extra space. That rules out the obvious "sort and scan" idea, which costs O(n log n).

Approach: start counting only at the beginning of a run

First, put every value into a HashSet<int>. This removes duplicates, and it lets you ask "is the number x present?" in constant time on average.

A naive use of the set would, for each number, walk upward (x + 1, x + 2, and so on) while the numbers exist. That repeats work: in [1, 2, 3, 4], starting at 1, 2, 3 and 4 would walk over the same elements again and again, giving O(n²) for a long run.

The fix is to walk only from the first number of each run. A number value starts a run exactly when value - 1 is not in the set. For every other number, the run it belongs to is measured from its true start, so there is no reason to measure it again. Each run is walked once, from its start to its end, and every number belongs to exactly one run. The inner while loops therefore touch each number at most once in total, so the whole algorithm is O(n).

On the first example, the set is {100, 4, 200, 1, 3, 2}. The numbers 100, 200 and 1 have no predecessor in the set, so they start runs of length 1, 1 and 4. The numbers 4, 3 and 2 do have a predecessor and are skipped.

Step by step

Create result, an int starting at 0. It stores the longest run so far, and 0 is the right answer for an empty array.
Fill a HashSet<int> called values. Loop over nums with foreach and call Add on each element. Adding a number already in the set does nothing.
Loop over values with foreach. Looping over the set instead of nums skips the duplicates for free.
Check !values.Contains(value - 1). Only then is value the first number of a run.
Start sequenceLength at 1. The run already contains value.
Extend with a while loop that runs as long as values.Contains(value + sequenceLength), incrementing sequenceLength. The expression value + sequenceLength is the next number the run needs, so the loop stops at the first missing one.
Update the best length with Math.Max(result, sequenceLength), still inside the if.
Return result after the loop.

The solution in C#

class Solution {

    public int LongestConsecutive(int[] nums) {
        int result = 0;
        HashSet<int> values = new HashSet<int>();
        foreach (int value in nums) {
            values.Add(value);
        }

        foreach (int value in values) {
            if (!values.Contains(value - 1)) {
                int sequenceLength = 1;
                while (values.Contains(value + sequenceLength)) {
                    ++sequenceLength;
                }
                result = Math.Max(result, sequenceLength);
            }
        }
        return result;
    }
};

C# details:

Two loops, one name. Both foreach loops declare value. That is legal because each loop variable is scoped to its own loop, and the first loop has ended before the second begins.
Do not modify a collection while iterating it. The second loop only reads values. Calling Add or Remove on the set inside the foreach would throw an InvalidOperationException.
Integer limits. value - 1 and value + sequenceLength are plain int arithmetic, and C# does not check for overflow by default. For int.MinValue, value - 1 silently wraps to int.MaxValue, so a set that contained both extreme values would be mistaken for one long run. Typical test data stays far from these limits.
The trailing ;. The semicolon after the class's closing brace is an empty declaration that C# accepts. It is not needed.

Complexity

Time: O(n). Building the set takes n constant-time insertions. In the second loop, the outer iterations run once per distinct value, and the inner while runs only for run starts, advancing through each run once. In total the number of Contains calls is at most about three per distinct value.

Space: O(n). The set holds up to n values.

Edge cases and common mistakes

Empty array. Both loops are skipped and the result stays 0.
Duplicates. [1, 1, 1] gives 1. Because the set stores each value once, repeated numbers cannot lengthen a run.
Negative numbers. [-2, -1, 0, 1] gives 4. Consecutive means differing by exactly 1, whatever the sign.
Skipping the start check. Without !values.Contains(value - 1) the answer is still correct but the time becomes O(n²) on a long run.
Sorting and counting. A sorted scan must skip equal neighbours, otherwise duplicates break the run count. The set avoids that problem.
Counting the run's size instead of its length. Count numbers, not gaps: a run from 5 to 7 has length 3, which is why sequenceLength starts at 1.

Testing

[100, 4, 200, 1, 3, 2] gives 4.
[0, 2, 0, 1, 2, 3, 1] gives 4.
[] gives 0.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free