## Problem

Given an array of numbers, find the length of the longest consecutive sequence

For example ,

Given the input

[100,4,200,1,3,2]

The longest consecutive sequence is [1,2,3,4]

So the length is 4.

Notice that the sequence need not be in order and can be scattered across the array.

Try out the solution here:

## Solution

Hint:

– Convert the array to a set

– use the logic : find if an element is present in the set or not

## Explanation:

Add the numbers to a set.

This ensures you have only unique elements to deal with.

For each element,

Check if the previous element (current element- 1) is present in the set or not

If it is not , then it means it is the first element in a new sequence.

Add 1 to it and see if it exists in set

Keep doing the above until you find consecutive elements.

Now you have found one sequence ,

Note down its length.

Similarly find other sequences and return the maximum sequence length.

## Code:

```
class Solution {
public int longestConsecutive(int[] nums) {
int maxStreak =0;
Set<Integer> numbers = new HashSet<Integer>();
for(int i:nums){
numbers.add(i);
}
for(int n:numbers){
if(!numbers.contains(n-1)){
int next = n +1;
while(numbers.contains(next)){
next++;
}
int currentStreak = next - n;
maxStreak = Math.max(currentStreak,maxStreak);
}
}
return maxStreak;
}
}
```

Algorithm:

1. Convert all numbers to a set

2. For each number in the set :

3. Check if (number-1) exists, If not then a new sequence can be started

4. Keep adding 1 to the number thus selected until you find the added number in the set

5. When the next number is not present in the set stop and calculate the length .

6. Find such lengths for all possible sequences and return the maximum length of the sequences

## Time complexity:

You iterate through all the elements once .

Even the while loop iteration checks only for the elements in a particular sequence.

So time complexity is O(n)

## Space complexity:

We create a new set which takes O(n) space , so space complexity is the same.

That’s it!

## Leave a Reply