# [LeetCode 128. Longest Consecutive Sequence ]()
### Daily challenge Jun 6, 2021 (MEDIAN)

>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.

:::info
**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.
:::

:::info
**Example 2:**
**Input:** nums = [0,3,7,2,5,8,4,6,0,1]
**Output:** 9
:::

:::warning
**Constraints:**
* 0 <= nums.length <= 105
* -109 <= nums[i] <= 109
:::

---

### Approach 1 : Two Pointer & Sort :bulb:
**`32 ms ( 97.36% )`** **`O(nlogn)`**

* sort `nums` in non-decreasing order。
* 使用兩個 pointers ( left & right ) 分別代表 Sequence 的開頭與結尾。
* **`temp`** 紀錄當前的數值。
>* **`nums[right] == temp`** ---> 相同數值不用重複計算。
>* **`nums[right] == temp + 1`** ---> `count + 1`。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int MAX = 0;
        
        int left = 0, right;
        while(left < nums.size()){
            int temp = nums[left];
            int count = 1;
            for(right=left+1; right<nums.size(); right++){
                if(nums[right] == temp)   continue;
                else if(nums[right] == ++temp)    count++;
                else    break;
            }
            
            left = right;
            MAX = max(MAX, count);
        }
        
        return MAX;
    }
};

### Approach 2 : Hash Set :book:
**`60 ms ( 82.97% )`** **`O(N)`**

* 使用 **`unordered_set`** 紀錄 `nums` 中出現的 `element`。
* 若 **`list.find(number - 1) == list.end()`**，就表示此段 `Sequence` 已經判斷過，無須再次計算。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> list;
        
        for(int i=0; i<nums.size(); i++){
            list.insert(nums[i]);
        }
        
        int MAX = 0;
        for(auto number : list){
            if(list.find(number - 1) == list.end()){    // avoid redundant computations
                int count = 1;
                int next = number + 1;
                while(list.find(next++) != list.end())  count++;
                MAX = max(MAX, count);
            }      
        }
        
        return MAX;
    }
};