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.