Given an unsorted integer array nums, return the length of the longest run of consecutive integer values it contains. Consecutive means values, not positions: [100, 4, 200, 1, 3, 2] contains the run 1, 2, 3, 4. Duplicates do not lengthen a run. Your algorithm must run in O(n) — sorting first is the answer this problem exists to beat.
Examples
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: the longest run is 1, 2, 3, 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Explanation: 0 through 8; the second 0 changes nothing.
Example 3:
Input: nums = [9]
Output: 1
Example 4:
Input: nums = [1,2,0,1]
Output: 3
Constraints
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Prerequisites
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide. Array traversal, and the habit of asking what a second pass buys over a nested loop.
How to think about it
1. Sort First
Intuition
Sorting puts consecutive values next to each other, and one walk measures the runs. It answers the question and is the natural first idea — but sorting costs O(n log n), and the problem exists to ask for better.
Algorithm
1. Sort the array. 2. Walk it, extending the current run when a value is exactly one more than the previous. 3. Skip equal neighbours — duplicates do not lengthen a run. 4. Track the longest run seen.
Time & Space
Time O(n log n) for the sort. Space O(1) beyond sorting.
2. Hash Set, Start of Run Only Optimal
Intuition
Sorting arranges every value when the question only needs to know where runs BEGIN. A value starts a run exactly when its predecessor is absent — a set answers that in constant time on average, and each run is then walked once. Every value is touched at most twice, so the nested-looking walk is still linear.
Algorithm
1. Put every value in a set. 2. For each value n, ask whether n-1 is missing — if it is, n starts a run; otherwise it is mid-run, not a start. 3. From each start, count upward while n+1, n+2, ... are present. 4. Keep the longest count.
Time & Space
Time O(n) — the inner walk runs once per run, not once per value. Space O(n) for the set.