# Data Structures & Algorithms in Java – Longest Consecutive Sequence

## 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:

Leetcode

## 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){

}

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!

Posted

in

by