128. Longest Consecutive Sequence
1. Description
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.
2. Example
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
3. Constraints
- 0 <= nums.length <= $10^5$
- -$10^9$ <= nums[i] <= $10^9$
4. Solutions
Hash Table
n = nums.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
int longestConsecutive(const vector<int> &nums) {
unordered_map<int, int> nums_occur;
for (int num : nums) {
nums_occur[num] = 1;
}
int max_length = 0;
for (int i = 0; i < nums.size(); ++i) {
int left = nums[i];
if (nums_occur[left] == 0) {
continue;
}
while (nums_occur[left] == 1) {
--left;
}
int length = 0;
for (++left; nums_occur[left] == 1; ++left) {
++length;
nums_occur[left] = 0;
}
max_length = max(length, max_length);
}
return max_length;
}
};