128. Longest Consecutive Sequence: Hashset
The O(n) constraint forces us to look into O(1) lookups - either a dict or set.
The key to this question is to intuitively think of a way to reliably find consecutive sequences in 1 pass.
todo: find an intuitive way to recall x-1.
1class Solution:
2 def longestConsecutive(self, nums: List[int]) -> int:
3 nums_set = set(nums)
4 result = 0
5
6 for num in nums_set:
7 if num - 1 not in nums_set:
8 streak = 1
9
10 while num + streak in nums_set:
11 streak += 1
12
13 result = max(result, streak)
14
15 return result
#Neetcode150 #Array #Hashing #Python