> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/128.-longest-consecutive-sequence.md).

# 128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(*n*) complexity.

**Example:**

```
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
```

```cpp
// Hashset
int longestConsecutive(vector<int>& nums) { // time: O(n); space: O(n)
    unordered_set<int> st(nums.begin(), nums.end());
    int res = 0;
    for (int num : nums) {
        if (!st.count(num)) continue;
        st.erase(num);
        int prev = num - 1, next = num + 1;
        while (st.count(prev)) {
            st.erase(prev--);
        }
        while (st.count(next)) {
            st.erase(next++);
        }
        res = max(res, next - prev - 1);
    }
    return res;
}
```

```cpp
// Hashmap
int longestConsecutive(vector<int>& nums) { // time: O(n); space: O(n)
    unordered_map<int, int> m;
    int res = 0;
    for (int num : nums) {
        if (m.count(num)) continue;
        int left = m.count(num - 1) ? m[num - 1] : 0;
        int right = m.count(num + 1) ? m[num + 1] : 0;
        int sum = left + 1 + right;
        m[num] = sum;
        res = max(res, sum);
        m[num - left] = sum;
        m[num + right] = sum;
    }
    return res;
}
```