mediumHashingPattern: Hash Set
Longest Consecutive Sequence Solution
Problem Statement
Given an unsorted array of integers, find the length of the longest consecutive sequence.
Examples
Example 1:
Input:[100, 4, 200, 1, 3, 2]
Output:4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]
Example 2:
Input:[0,3,7,2,5,8,4,6,0,1]
Output:9
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]
Constraints
- 0 <= n <= 10^5
- -10^9 <= arr[i] <= 10^9
Time: O(N) Space: O(N)
Use HashSet. For each element, check if it's the start of a sequence (if num-1 is not in set). If it is, count upwards in the set. Time O(N), Space O(N).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.