Longest Chain of Consecutive Numbers
Given an unsorted array of integers nums, return the length of the
longest run of consecutive integers (i.e., integers that form a
sequence like x, x+1, x+2, ... with no gaps). The numbers do not
need to be contiguous in the original array, and duplicates should be
treated as a single value.
Your algorithm must run in O(n) time.
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: The longest run is [0, 1, 2, 3, 4, 5, 6, 7, 8].
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
Sorting would give an O(n log n) solution, but we can do O(n) using a
hash set for O(1) membership checks. The key trick is to only start
counting a run from a number that is the start of a run — that is,
a number x such that x - 1 is not in the set. Every element
still gets visited, but the inner "count up from here" loop only
ever runs for true run starts, so the total work across all
iterations stays linear.
def longest_consecutive_chain(nums: list[int]) -> int:
num_set = set(nums)
longest = 0
for x in num_set:
if x - 1 in num_set:
continue # not a run start, skip
length = 1
current = x
while current + 1 in num_set:
current += 1
length += 1
longest = max(longest, length)
return longest
Complexity: O(n) time — although there's a nested while loop,
each number is only ever extended from once (only from its run's
start), so the total number of while iterations across the whole
algorithm is bounded by n. O(n) space for the hash set.
Share this question