Longest Consecutive Sequence
Medium · Arrays & Hashing · Array · Hash Table · Union Find
Problem
Given an unsorted array nums, return the length of the longest run of consecutive integers it contains. The numbers need not be adjacent in the array.
Your solution must run in O(n).
Examples
Input: nums = [100,4,200,1,3,2] Output: 4
1, 2, 3, 4 form the longest run.
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
0 through 8.
Constraints
- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- O(n) time is required
Approaches
- Sort, then walk — time O(n log n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
