128. Longest Consecutive Sequence
## description
## 128. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
1Input: nums = [100,4,200,1,3,2]
2Output: 4
3Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.Example 2:
1Input: nums = [0,3,7,2,5,8,4,6,0,1]
2Output: 9Example 3:
1Input: nums = [1,0,1,2]
2Output: 3- –0 <= nums.length <= 105
- –-109 <= nums[i] <= 109
Constraints:
## notes
### Intuition
A number is the start of a consecutive sequence if there's no number exactly one less than it in the array. Once we identify a sequence start, we can count how long the sequence extends by checking for consecutive numbers.
### Implementation
Store all numbers in a hashmap for O(1) lookup. Iterate through the array and check if each number is a sequence start (num - 1 not in map). If it is, walk forward counting consecutive numbers (num + 1, num + 2, etc.) and track the maximum length found.
### Edge-cases
Duplicates can cause us to process the same sequence start multiple times. Initialize the hashmap with all False values and mark a sequence start as True once processed to avoid redundant work.
- –Time: O(n) — each number is part of at most one sequence traversal
- –Space: O(n) — hashmap stores all numbers
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def longestConsecutive(self, nums: List[int]) -> int:
5 map = {}
6 for num in nums:
7 map[num] = False
8
9 max_sequence = 0
10 for num in nums:
11 is_sequence_start = num - 1 not in map
12 if is_sequence_start and map[num] == False:
13 map[num] = True # mark this sequence start as processed
14 length = 0
15 curr = num
16 while curr in map:
17 curr += 1
18 length += 1
19 max_sequence = max(max_sequence, length)
20
21
22 return max_sequence
23
24
25
26
27if __name__ == "__main__":
28 # Include one-off tests here or debugging logic that can be run by running this file
29 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
30 solution = Solution()
31