Array & Hashing
30. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Examples
Example 1
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
# Given an unsorted array of integers, return the length of the longest consecutive sequence.
# Must run in O(n) time.
nums = [100, 4, 200, 1, 3, 2]
# Create a set for O(1) lookups
num_set = set(nums)
longest = 0
for num in num_set:
# Only start counting if num is the beginning of a sequence
if num - 1 not in num_set:
length = 1
# Count consecutive numbers forward
while num + length in num_set:
length += 1
longest = max(longest, length)
print(longest) # 4Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help