Arrays & Hashing · 052Medium
Longest Consecutive Sequence
Given an unsorted array nums, return the length of the longest sequence of consecutive integers in it. The elements need not be adjacent in the array. Must run in O(n) time.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- Your solution must run in O(n) time.
Examples
longestConsecutive([100, 4, 200, 1, 3, 2]) -> 4 // [1,2,3,4] longestConsecutive([0,3,7,2,5,8,4,6,0,1]) -> 9 longestConsecutive([]) -> 0 // empty array longestConsecutive([5]) -> 1 // single element longestConsecutive([1, 2, 0, 1]) -> 3 // the duplicate 1 does not inflate [0,1,2] longestConsecutive([9, 1, 4, 7, 3, -1, 0, 5, 8, -1, 6]) -> 7 // [3..9] beats [-1,0,1]
Edge cases
- Empty array returns 0.
- Duplicates must not inflate the count.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — sort and scan for runs. Correct, but misses the target.
- Target
- O(n) time, O(n) space — put everything in a Set, and only start counting from x when x-1 is absent, so each run is walked once.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/052-longest-consecutive-sequence.js ./practice c 052