Longest Consecutive Sequence

Share

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

Contents

Solution 1 - Store numbers into HashSet, find the starting of a sequence then find the longest consecutive sequence

In the problem statement, we were asked to find a solution with O(n) time complexity, so in this approach first we are going to store elements into a HashSet, then loop through every element num from array and check if num-1 exists in the HashSet, if it exists that means this number is not the starting element of the consecutive sequence and if it does not exist then the number is a starting element of a consecutive sequence and then we will find how long that sequence can be and finally take the longest sequence found.

Java
import java.util.HashSet;
import java.util.stream.IntStream;

public class LongestConsecutiveSequence {

    /**
      *
      * First store elements into a HashSet, then loop through each element in the array and find if
      * previous number (num-1) exists in set, if it exists that means that is not the first number of 
      * a starting sequence, and if previous number does not exist, then this is the first number of a 
      * starting sequence.
      *
      * When you find a starting number of sequence, keep checking if next number exists (num+1) 
      * and find the longest
      */
    static int longestConsecutiveUsingHashSet(int[] nums) {
        HashSet<Integer> set = new HashSet<>(nums.length);
        IntStream.of(nums).forEach(set::add);
        
        int longest =0;
        for(int num: nums) {
            if(!set.contains(num-1)) {
                // if the previous number is not in the set, that means this is the starting of sequence.
                int currentLong = 1;
                int currentNum = num;
                while(set.contains(currentNum+1)) {
                    currentLong++;
                    currentNum++;
                }
                if(currentLong >longest) {
                    longest = currentLong;
                }
            }
        }
        return longest;
    }


}
Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length.
Space complexity: O(n) since we are storing input array into a HashSet.

Above implementations source code can be found at GitHub link for Java code