The problem
Given an unsorted array of integers nums, return the length of the longest run of consecutive values — like 1, 2, 3, 4 — that can be made from its elements. The run does not have to appear in order in the array.
It must run in O(n) time.
Examples
01
- Input
nums = [100, 4, 200, 1, 3, 2]
- Output
4
02
- Input
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
- Output
9
Constraints
- 0 ≤ nums.length ≤ 10⁵
- −10⁹ ≤ nums[i] ≤ 10⁹
The idea
Sorting would find runs, but costs n log n. Put every number into a hash set instead, so “is x in the array?” takes one step.
A number x starts a run exactly when x − 1 is not in the set. Only from those starts, count upward — x + 1, x + 2, … — while the numbers exist. Each number is counted by the one run it belongs to, so all the counting together is linear.
- Time
- O(n) — each number is visited a constant number of times
- Space
- O(n) — the set
Solution · every language run against every case
class Solution: def longestConsecutive(self, nums: List[int]) -> int: have = set(nums) best = 0 for x in have: if x - 1 in have: continue # not the start of a run: its run is counted from its start length = 1 while x + length in have: length += 1 best = max(best, length) return best