Longest Consecutive Sequence

Return the length of the longest run of consecutive integers in an unsorted array, in O(n) time.

A way to picture it

Numbers are rungs scattered around a building site. Sorting them would be slow. Instead, throw them all in a bucket you can search instantly, and only start climbing from a rung that has nothing directly below it.

How to approach it

Put everything in a HashSet. Only start counting at x when x − 1 is missing, then walk x + 1, x + 2… Each run is walked exactly once.

Example

Input: {"nums":[100,4,200,1,3,2]}. Output: 4.

Complexity: O(n) time and O(n) space. Every number is part of exactly one run, and each run is walked once from its start.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.