Foundations
Longest Consecutive Sequence
Set-membership walks: only chain starts (no predecessor) begin a walk, so each number is visited at most twice - O(n) for the longest run of consecutive integers.
Problem
Uptime monitors bucket event timestamps into consecutive-second windows, and analytics needs the longest streak of back-to-back seconds with activity - order unknown, duplicates allowed. Given an unsorted array of integers, find the length of the longest run of consecutive integers that can be formed from its values, in O(n) time.
Example 1:
Input: nums = [15, 7, 8, 9, 12, 3]
Output: 3
Explanation: the consecutive runs are 7-8-9, 12, 15, and 3; the longest has length 3.Example 2:
Input: nums = [12, 14, 13, 30, 28, 29, 11]
Output: 4
Explanation: 11-12-13-14 form a run of length 4; 28-29-30 reach only 3.Example 3:
Input: nums = [11, 13, 15, 17]
Output: 1
Explanation: no two values are adjacent; every run is a single number.Constraints:
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
Solution Breakdown
Approach - hash-set membership with chain-start-only walks.
The consecutive-run question needs exactly one primitive: "is value v present?" Ordering the input is overkill - a hash set answers the membership probe in O(1) average, and the chain structure can be discovered by probing v-1, v+1, v+2, ... directly. The subtlety is bounding the work. A naive "walk from every element" is quadratic: a run of length L would be re-walked L times. The fix is to start walks only at chain starts - values whose num - 1 is absent from the set. Every chain has exactly one start, so exactly one walk measures it end to end. Every element is then touched a constant number of times: one predecessor check in the outer loop, plus one step by the single walk that crosses it. That is the amortized argument that makes the nested while loop O(n) overall.
Trace [12, 14, 13, 30, 28, 29, 11]: the set holds {11..14, 28, 29, 30}. The outer loop skips 12, 13, 14 (their predecessors are present) and fires walks at 11 and 28: 11 -> 12 -> 13 -> 14 measures length 4; 28 -> 29 -> 30 measures 3. best = 4. Duplicates never matter because the set deduplicates; negatives work identically since the arithmetic is sign-agnostic.
Edge cases - an empty array has no chains and returns 0; all-duplicate input collapses to a singleton chain; spread values like [11, 13, 15, 17] make every element a start whose walk immediately ends - best 1.
Complexity - O(n) average time: O(n) to build the set, then at most 2n membership probes across the start checks and the walks. O(n) space for the set - the whole input must be queryable simultaneously, so this cannot be done in sublinear space. The sort-based alternative is correct but O(n log n), which the problem explicitly disallows.
Done reading? Mark it so it sticks in your dashboard.