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