Longest Consecutive Sequence

Given an unsorted array of integers, return the length of the longest run of consecutive integers (in any order in the array). Must run in O(n).

Example

Input: 100 4 200 1 3 2 Output: 4 (the sequence 1, 2, 3, 4)

Approach

Put every number in a set. For each number that is the start of a sequence (i.e. number - 1 is not in the set), count forward (number + 1, number + 2, …) while those values exist in the set. Every number is visited at most twice total, keeping it O(n) despite the nested-looking loop.