Longest Consecutive Sequence
- 1 min read
- Array
- LC-Medium
3 years ago
Solution
- Convert array to set, and for each number, keeping incrementing a counter if num + 1 in nums
- If num - 1 is not in nums, then the number is not the beginning of a sequence, so skip
| Time | Space | Explanation |
|---|---|---|
O(m) | O(?) |
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
nums = set(nums)
ans = 1
for num in nums:
if num - 1 in nums:
continue
cur = num
while cur + 1 in nums:
cur = cur + 1
ans = max(ans, cur - num + 1)
return ans