Description
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.
Solutions
1. Hash Table
# Time: O(n)
# Space: O(n)
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
hash_map = collections.defaultdict(int)
res = 0
for num in nums:
# drop duplicates
if num in hash_map:
continue
left = hash_map.get(num - 1, 0)
right = hash_map.get(num + 1, 0)
cur_max = left + right + 1
hash_map[num] = hash_map[num - left] = hash_map[num + right] = cur_max
res = max(res, cur_max)
return res
# 68/68 cases passed (60 ms)
# Your runtime beats 43.04 % of python3 submissions
# Your memory usage beats 96.3 % of python3 submissions (13.8 MB)
2. Upgrade
# Time: O(n)
# Space: O(n)
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums = set(nums)
res = 0
for x in nums:
if x - 1 not in nums:
y = x + 1
while y in nums:
y += 1
res = max(res, y - x)
return res
# 68/68 cases passed (56 ms)
# Your runtime beats 66.84 % of python3 submissions
# Your memory usage beats 96.3 % of python3 submissions (13.8 MB)