# 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
**Example 3:**
**Input:** nums = [1,0,1,2]
**Output:** 3
**Constraints:**
- `0 <= nums.length <= 105`
- `-109 <= nums[i] <= 109`
# Approaches
1. Brute Force
2. Sorting and Single Loop
3. Hash Table
## Brute Force
The idea is to loop through each number and check if the next number exists. If the next number exists increase the current streak or else update the result streak to current streak and reset current streak to 0 and start looping through the array.
The Problem with this approach is Time Complexity of O(n^2)
```ts
function longestConsecutive(nums: number[]): number {
let result = 0
// This will remove duplicates in the array
const store = new Set(nums)
// Loop through each num in the array
for (let num of nums) {
let currentStreak = 0
let currentNum = num
while(store.has(currentNum)) {
currentNum++
currentStreak++
}
result = Math.max(result, currentStreak)
}
return result
}
```
## Sorting and Single Loop
The idea here is to sort the array with O(n log n) and then iterate over the array. While iterating if the current and previous number is same go to next position and check if both are not same and previous one is less than 1 to current. If so increment currentstreak or else break the current streak and update result with current streak. Start the current streak with 1 again
```ts
function longestConsecutive(nums: number[]): number {
if(nums.length === 0) {
return 0
}
// Sort nums array
nums.sort((a, b) => a - b)
// Initialize Variable
let longestLength = 1
let currentLength = 1
// Loop Through array
for (let i = 1; i < nums.length; i++) {
if(nums[i] !== nums[i - 1]) {
// if numbers are consecutive increment
if(nums[i] === nums[i -1] + 1) {
currentLength++
} else {
longestLength = Math.max(longestLength, currentLength)
longestLength = 1
}
}
}
return Math.max(longestLength, currentLength)
}
```
## Hash Table Approach
The approach is to store all the values in a set, so search would be O(1).
There are two types of numbers in the sequence
Type 1: The number is start of the sequence
Type 2: The number is part of the sequence
We need to find the number that is start of the sequence and increment until there is no sequence
```ts
function longestConsecutive(nums: number[]): number {
const set = new set(nums)
let longestLength = 0
for (let num of set) {
// if set doesn't have previous num sequence this is where we start
if (!set.has(num -1)) {
let currentLength = 0
while(set.has(num + currentLength)) {
currentLength++
}
longestLength = Math.max(currentLength, longestLength)
}
}
return longestLength
}
```