# 128 Longest Consecutive Sequence

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

For example,

```
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
```

Your algorithm should run in O(n) complexity.

**The Idea:** First we store all the numbers into a hash table. We'll use this table to jump around finding consecutive numbers. To avoid making this N^2, we need to impose some rules on how will jump from one integer from the next. The process goes as follows. For each number of the array, we attempt to follow a streak. I've arbitrarily decided to look up acending sequences. I can identify the start of a streak when there exists a number + 1 of the present number, and their doesnt exist a smaller number - 1 than the present number. If these conditions hold true, then I know that I've identified the smallest number of a potentially long steak. Now, I can iterate through this streak by identifing num + 1 through the hash table. As I do, I mark said value as visited. This is to ensure that I dont try to and reidentify the loop (as visited indicates that the streak was already identified as part of another streak that was already counted). So iterating through this streak, I mark the integers visited, and increment the streak length. At the end of the streak, I update the maximum streak, and until all streaks are identified in the sequence.

**Complexity:** O(2n) time and O(n) space

```cpp
int longestConsecutive(vector<int>& nums) {
    unordered_map<int, bool> m;
    m.reserve(nums.size());
    for (int num : nums) 
        m[num] = false;

    int max_streak = 0;
    for (int num : nums) {
        int cur_streak = 1;
        if (m.find(num + 1) != m.end() && !m[num + 1] &&
            m.find(num-1) == m.end()) {
            while (m.find(num + 1) != m.end() && !m[num + 1]) {
                m[num] = true;
                cur_streak++;
                num++;
            }
        }
        max_streak = max(max_streak, cur_streak);
    }

    return max_streak;
}
```

**Python**

The idea is the same. For every number, count the number of ascending elements in front of it, as well as descending elements behind it. These numbers are to be a part of a single streak. For every streak, we record and maintain the maximum length. Each element in the list will be visited once and be identified as part of a unique streak, so the complexity is linear.

```python
class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = set(nums)
        max_streak = 0
        visited = set()
        for num in nums:
            # find the longest streak to the right
            visited.add(num)
            cur_streak_right = 1
            cur_num = num + 1
            while cur_num in s and cur_num not in visited:
                visited.add(cur_num)
                cur_streak_right += 1 
                cur_num += 1

            # find the longest streak to the left
            cur_streak_left = 0
            cur_num = num - 1
            while cur_num in s and cur_num not in visited:
                visited.add(cur_num)
                cur_streak_left += 1 
                cur_num -= 1

            max_streak = max(cur_streak_left + cur_streak_right, max_streak)
        return max_streak
```