Longest consecutive sequence

Find the length of the longest run of consecutive integers, in O(n), without sorting.

The idea

Put every number into a hash set, then only start counting a run from a number that has no predecessor in the set (x - 1 is missing). Every run therefore gets counted exactly once, starting from its smallest member, which keeps the whole scan O(n) even though it looks nested.

Code

public static int LongestConsecutive(int[] a) {
    var set = new HashSet<int>(a);
    int best = 0;
    foreach (int x in set) {
        if (set.Contains(x - 1)) continue;
        int len = 1;
        while (set.Contains(x + len)) len++;
        best = Math.Max(best, len);
    }
    return best;
}

Tips

• Skipping x whenever x - 1 is in the set is what keeps this O(n): without it, every number inside a run would restart the count from scratch.
• Build the set once up front; duplicate values in the input collapse into it automatically.

In the .NET library

It looks like an O(n^2) nested loop, but across the whole run of the algorithm the inner while only ever advances through each number once, since a number is only ever visited from the start of its own run.