> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/arrays ]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: done]
> [link:: https://leetcode.com/problems/longest-consecutive-sequence/]
> [up:: [[Leetcode MOC]]]
## Problem
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:**
**Input:** nums = [100,4,200,1,3,2]
**Output:** 4
**Explanation:** The longest consecutive elements sequence is `[1, 2, 3, 4]`. Therefore its length is 4.
**Example 2:**
**Input:** nums = [0,3,7,2,5,8,4,6,0,1]
**Output:** 9
**Constraints:**
- `0 <= nums.length <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
## Solution
### Mine
#### Python
```python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
set_nums = set(nums)
max_sequence = 0
for num in set_nums:
if num - 1 not in set_nums:
current_count = 1
# Could also do num + current_count and only increment that
while num + 1 in set_nums:
current_count += 1
num += 1
max_sequence = max(max_sequence, current_count)
return max_sequence
```
#### Rust
### Neetcode's
```python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
longest = 0
for n in nums:
if (n - 1) not in numSet:
length = 0
while (n + length) in num_set:
length += 1
longest = max(length, longest)
return longest
```
## Things I Learned
### Neetcode
![[Pasted image 20230207222137.png]]
Visualize it like a human would. Notice we have 3 sequences. We can convert this to code, without sorting.
Notice this: each starting point of a sequence has no left neighbor. First, turn array into set.
For each item, check to see if $item - 1$ is in set (because it's a set, lookup is $O(N)$). If it isn't, then the item is the start of a sequence. If the item is the start of a sequence, check to see if $item + 1$ is in set, and keep going, keeping track of the size of the sequence. ^np61r7
We visit each node at most twice, giving $O(2n) \approx O(n)$. Memory $O(n)$ for extra space by set.
## Scratchpad
Can't do a sort because that would be $O(n\:log\:n)$ time.
~~One kind of clunky way would be to create a prebuilt array where each location represents a value with its index. The universe of numbers is only 219, we can build a 219-element array of Nones, then for each number, change that index's value to True. Then do a pass through that and get largest consecutive Trues.~~
The universe of numbers is NOT 219.
Pausing video [[128. Longest Consecutive Sequence#^np61r7|here]] because I think I can solve it from here.