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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_map<int, int> mp;//number, maxLen int ret = 0; for(auto n:nums) { if(mp.count(n)==0) { int len = 1; if(mp.count(n-1)!=0 && mp.count(n+1)!=0){ int left = n-mp[n-1]; int right = n+mp[n+1]; len = mp[n-1]+mp[n+1]+1; mp[left] = len; mp[right] = len; }else if(mp.count(n-1)!=0){ len = mp[n-1]+1; mp[n+1-len] = len; }else if(mp.count(n+1)!=0){ len = mp[n+1]+1; mp[len+n-1] = len; } mp[n] = len; ret = max(ret, len); } } return ret; } }; class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_map<int, int> hash;//number, length int ret = 0; for(auto n:nums){ if(hash.count(n)) continue; int nl = 0, nr = 0; if(hash.count(n-1)) nl = hash[n-1]; if(hash.count(n+1)) nr = hash[n+1]; int len = nl+nr+1; hash[n] = len; hash[n-nl] = len; hash[n+nr] = len; ret = max(ret, len); } return ret; } }; class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> ns(nums.begin(), nums.end()); int ret = 0; for(auto n:ns){ if(ns.count(n-1)==0){ int tmp = 0; while(ns.count(n+tmp)){ tmp++; } ret = max(ret, tmp); } } return ret; } };