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.

Difficulty: interview

Starter code:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         longest_streak = 0
         num_set = set(nums)
         for num in num_set:
             if num - 1 not in num_set:
                 current_num = num
                 current_streak = 1
                 
                 while current_num + 1 in num_set:
                     current_num += 1
                     current_streak += 1
                     
                 longest_streak = max(longest_streak, current_streak)
         return longest_streak

class Solution(object):
     def radix_sort(self, nums):
         if not nums:
             return []
         n_rounds = 0
         num_strs = [str(num) for num in nums]
         n_rounds = max([len(num_str) for num_str in num_strs])
         buckets = [[] for i in range(10)]
         for i in range(n_rounds):
             for num_str in num_strs:
                 if i < len(num_str):  # get the last ith digit
                     radix = ord(num_str[-i - 1]) - ord('0')
                 else:
                     radix = 0
                 buckets[radix].append(num_str)
             num_strs.clear()
             for bucket in buckets:
                 num_strs.extend(bucket)
                 bucket.clear()
         return [int(num_str) for num_str in num_strs]
 
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         pos_nums = [num for num in nums if num >= 0]
         neg_nums = [-num for num in nums if num < 0]
         pos_nums = self.radix_sort(pos_nums)
         neg_nums = self.radix_sort(neg_nums)
         nums = [-num for num in reversed(neg_nums)] + pos_nums
         n = 1
         max_n = 1
         for i in range(1, len(nums)):
             if nums[i] - nums[i - 1] == 1:
                 n += 1
                 if n > max_n:
                     max_n = n
             elif nums[i] == nums[i - 1]:
                 continue
             else:
                 n = 1
         return max_n


class Solution:
     def longestConsecutive(self, a):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums = set(a)
         maxlen = 0
 
         while nums:
             first = last = nums.pop()
             while first - 1 in nums:
                 first -= 1
                 nums.remove(first)
 
             while last + 1 in nums:
                 last += 1
                 nums.remove(last)
 
             maxlen = max(maxlen, last - first + 1)
 
         return maxlen


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         # init dict, set default to 0
         length_dict = {key: 0 for key in nums}
         longest = 0
         
         for i in nums:
             #print("i = "+str(i))
             if length_dict[i]:
                 #print("skip "+str(i)) # already done
                 continue
             
             length = 1
             length_dict[i] = 1
             #print(length_dict)
             
             j = i + 1
             while j in length_dict:
                 #print("+:"+str(j))
                 length_dict[j] = 1
                 length += 1
                 j += 1
             
             j = i - 1
             while j in length_dict:
                 #print("-:"+str(j))
                 length_dict[j] = 1
                 length += 1
                 j -= 1
             
             longest = max(longest, length)
         
         return longest


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         
         if len(nums) == 0:
             return 0
         
         seen = set()
         heads = set()
         tails = set()
         forward = dict()
         reverse = dict()
         
         for n in nums:
             
             if n in seen:
                 continue
             else:
                 seen.add(n)
             
             if n-1 not in tails and n+1 not in heads:
                 heads.add(n)
                 tails.add(n)
                 forward[n] = n
                 reverse[n] = n
             
             if n-1 not in tails and n+1 in heads:
                 heads.remove(n+1)
                 heads.add(n)
                 tail = forward[n+1]
                 del forward[n+1]
                 forward[n] = tail
                 reverse[tail] = n
             
             if n-1 in tails and n+1 not in heads:
                 tails.remove(n-1)
                 tails.add(n)
                 head = reverse[n-1]
                 del reverse[n-1]
                 reverse[n] = head
                 forward[head] = n
             
             if n-1 in tails and n+1 in heads:
                 head = reverse[n-1]
                 tail = forward[n+1]
                 heads.remove(n+1)
                 tails.remove(n-1)
                 del forward[n+1]
                 del reverse[n-1]
                 forward[head] = tail
                 reverse[tail] = head
         
         
         diffs = [v - k + 1 for (k,v) in list(forward.items())]
         maxRun = max(diffs)
         
         return maxRun
                 
                 
                 
             


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         flag_map = {}
         for x in nums:
             flag_map[x] = False
         
         result = 0
         for x in nums:
             count = 1
             tmp = x + 1
             flag_map[x] = True
             while True:
                 if tmp in flag_map and not flag_map[tmp]:
                     count = count + 1
                     flag_map[tmp] = True
                     tmp = tmp + 1
                 else:
                     break
                     
             tmp = x - 1
             while True:
                 if tmp in flag_map and not flag_map[tmp]:
                     count = count + 1
                     flag_map[tmp] = True
                     tmp = tmp - 1
                 else:
                     break
                     
             result = max(result, count)
             
         return result

class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         from collections import Counter
         def find(x,maps):
             if x in maps:
                 maps[x]=find(maps[x],maps)
             else:
                 return x
             return maps[x]
         def join(x,y,maps):
             i,j=find(x,maps),find(y,maps)
             if i!=j:
                 if i<j:
                     maps[j]=i
                 else:
                     maps[i]=j
         if not nums:
             return 0
         visited={}
         maps={}
         for i in nums:
             if i in visited:
                 continue
             if i not in visited and i-1 in visited:
                 join(i-1,i,maps)
             if i not in visited and i+1 in visited:
                 join(i+1,i,maps)
             if i not in visited:
                 visited[i]=1
         if not maps:
             return 1
         for key in list(maps.keys()):
             join(maps[key],key,maps)
         d=Counter(list(maps.values()))
         return max(d.values())+1


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums = set(nums)
         best = 0
         for x in nums:
             if x - 1 not in nums:
                 y = x + 1
                 while y in nums:
                     y += 1
                 best = max(best, y - x)
         return best
             


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         s = set(nums)
         
         longest = 0
         for i in s: 
             if(i-1 in s):
                 continue
             sequence = 1
             num = i
             while(num+1 in s):
                 sequence += 1
                 num += 1
             longest = max(longest, sequence)
             
         return longest

class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max_count = 0
         s = set(nums)
         for i in nums:
             cnt = 1
             tmp = i-1
             while tmp in s:
                 cnt += 1
                 s.discard(tmp)
                 tmp -= 1
                 
             tmp = i+1
             while tmp in s:
                 cnt += 1
                 s.discard(tmp)
                 tmp += 1
             
             max_count = max(max_count, cnt)
             
         return max_count


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         
         longest = 1
         current = 1
         
         nums.sort()
         
         n = len(nums)
         for i in range(1, n):
             if nums[i] != nums[i-1]:
                 if nums[i] == nums[i-1] + 1:
                     current += 1
                 else:
                     longest = max(longest, current)
                     current = 1
                     
         return max(longest, current)


class Solution(object):
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         if not nums:
             return 0
         nums_set = set(nums)  # dedup and build a map for fast lookup
         # remove numbers which are not connected with any other numbers
         for num in list(nums_set):
             if (num - 1) not in nums_set and (num + 1) not in nums_set:
                 nums_set.remove(num)
 
         # now nums_set only contains groups of consecutive numbers
         # calculate the size of each group and find the largest group
         max_group_size = 1
         while nums_set:
             num = nums_set.pop()
             group_size = 1
             prev_num = num - 1
             while prev_num in nums_set:
                 group_size += 1
                 nums_set.remove(prev_num)
                 prev_num -= 1
             next_num = num + 1
             while next_num in nums_set:
                 group_size += 1
                 nums_set.remove(next_num)
                 next_num += 1
             if group_size > max_group_size:
                 max_group_size = group_size
         return max_group_size


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         nums.sort()
         max_length = 0
         count =0
         
         for idx, v in enumerate(nums):
             
             if count==0:
                 count+=1
                 max_length=max(max_length,count)
             if idx+1<len(nums):
                 n_v = nums[idx+1]
                 
                 if n_v==v+1:
                     count=count+1 
                 elif n_v==v:
                     continue
                     
                     
                 else:
                     max_length=max(max_length,count)
                     count = 0
         #deal with the end 
         max_length=max(max_length,count)
         return max_length
                 
                 


class Solution:
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         def union(uf, p, q):
             i, j = root(uf, p), root(uf, q)
             uf[i], uf[j] = min(i, j), min(i, j)
         def root (uf, p):
             while p != uf[p]:
                 uf[p] = uf[uf[p]]
                 p = uf[p]
             return p
         if len(nums) == 0:
             return 0
         ht = {}
         uf = [i for i in range(len(nums))]
         for i, n in enumerate(nums):
             if n not in ht:
                 ht[n] = i
             else:
                 continue
             m, o = n - 1, n + 1
             if m in ht:
                 union(uf, ht[m], i)
             if o in ht:
                 union(uf, ht[o], i)
         roots = {}
         for x in uf:
             r = root(uf, x)
             if r in roots:
                 roots[r] += 1
             else:
                 roots[r] = 1
         return max(roots.values())


class Solution:
     
     def longestConsecutive(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
 
         # unique elms in list
         elms = set()
 
         # prevent dup. effort during consecutive search
         visited = set()
         max_consecutive = 0
 
         for num in nums:
 
             elms.add(num)
 
         # look for all unique consecutive subsequences
         for num in nums:
 
             if num in visited:
 
                 continue
 
             visited.add(num)
 
             # elm by itself
             curr_consecutive = 1
             tmp = num - 1
 
             # number of consecutive elms before
             # this elm
             while tmp in elms:
 
                 visited.add(tmp)
                 curr_consecutive += 1
                 tmp -= 1
 
             tmp = num + 1
 
             # number of consecutive elms after
             # this elm
             while tmp in elms:
 
                 visited.add(tmp)
                 curr_consecutive += 1
                 tmp += 1
 
             if curr_consecutive > max_consecutive:
 
                 max_consecutive = curr_consecutive
 
         return max_consecutive