Given an unsorted integer array, return the length of the longest run of consecutive integers. e.g. [100,4,200,1,3,2] → 4 (for 1,2,3,4). Required: O(n) time, so no sorting.
Beating the obvious O(n log n) sort with a hash set, plus the key insight of only starting a count from a number that has no left-neighbour.
Sorting gives the answer trivially but costs O(n log n); the O(n) solution is a hash set with one clever guard. Put every number in a Set. Then for each number, only begin counting a streak if n-1 is NOT in the set — i.e. this number is the START of its run. From a start, walk n+1, n+2, … while they are present, counting length. The guard is what makes it linear: each number is the interior of exactly one streak and is walked only once (from its start), so total work is O(n) despite the nested loop. Recognition signal: 'longest consecutive/adjacent group with no ordering requirement' under an O(n) constraint → hash set for O(1) membership plus start-of-run detection to avoid recounting. Trades O(n) space for the speedup.
Longest consecutive grouping of values needed in O(n) (sorting disallowed) → dump into a Set and expand runs only from elements that have no predecessor.
Time O(n) · Space O(n)