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.

Source: leetcode | Difficulty: MEDIUM
Tags: Spanning trees

Data structures

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

Solutions:
class Solution:

	def longestConsecutive(self, nums):
		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):
					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):
		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):
		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):
		length_dict = {key: 0 for key in nums}
		longest = 0
		for i in nums:
			if length_dict[i]:
				continue
			length = 1
			length_dict[i] = 1
			j = i + 1
			while j in length_dict:
				length_dict[j] = 1
				length += 1
				j += 1
			j = i - 1
			while j in length_dict:
				length_dict[j] = 1
				length += 1
				j -= 1
			longest = max(longest, length)
		return longest


class Solution:

	def longestConsecutive(self, nums):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		if not nums:
			return 0
		nums_set = set(nums)
		for num in list(nums_set):
			if num - 1 not in nums_set and num + 1 not in nums_set:
				nums_set.remove(num)
		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):
		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
		max_length = max(max_length, count)
		return max_length


class Solution:

	def longestConsecutive(self, nums):

		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):
		elms = set()
		visited = set()
		max_consecutive = 0
		for num in nums:
			elms.add(num)
		for num in nums:
			if num in visited:
				continue
			visited.add(num)
			curr_consecutive = 1
			tmp = num - 1
			while tmp in elms:
				visited.add(tmp)
				curr_consecutive += 1
				tmp -= 1
			tmp = num + 1
			while tmp in elms:
				visited.add(tmp)
				curr_consecutive += 1
				tmp += 1
			if curr_consecutive > max_consecutive:
				max_consecutive = curr_consecutive
		return max_consecutive