Longest Consecutive Sequence
FreeArrays & hashingMedium8 of 75
The problem
Find the length of the longest run of consecutive integer values present in an unsorted array. Values in the run need not occupy adjacent positions.
Example
[12, 3, 1, 2, 20, 4, 2] → 4
Need a hint?
Start counting only at the smallest value of a run.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Insert all values into a set. For each unique x, skip it if x − 1 exists. Otherwise count x, x + 1, and so on until the run ends. Each value belongs to just one counted run; duplicates do not extend it.
Complexity
O(n) expected time and O(n) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.