Longest Consecutive Sequence

Chaitra Rai

·

Follow

2 min read

·

Nov 16, 2021

--

Listen

Share

Given an unsorted array, one has to return the length of the array subset with consecutive elements(Full Question)

• The first approach would be to iterate through the array and check for each element if the element+1 exists in the array
• if the element+1 number does exist we keep increasing a temporary count variable
• we do this for every element in the array and compare the end results of all the iteration to return the maximum out of all
• doing this for elements irrespective of the overlapping cases makes this approach not a very efficient one taking a lot of time for computation

public boolean arrayContains(int[] nums, int n){
    for(int num:nums){
        if(num==n)
            return true;
    }
    return false;
}
public int longestConsecutive(int[] nums) {
    int longestcount=0;
    int currentnum=0;
    int currentcount=0;
    if(nums.length==0)
        return 0;
    for(int num:nums){
        currentnum=num;
        currentcount=1;
        while(arrayContains(nums,currentnum+1)){
            currentnum+=1;
            currentcount+=1;
        }
        longestcount=Math.max(currentcount,longestcount);
    }
    longestcount=Math.max(currentcount,longestcount);
    return longestcount;
}

• The iteration happens in 3 loops: one to consider each element, one to examine the frequency of numbers in the subset, and another loop to check if the number+1 is present in the array
• The time complexity is O(n³) and exceeds the time limits on submission
• A number would be automatically adjacent to a consecutive number in an array if its sorted
• We could improve the algorithm by sorting the array and iterating it and also include a condition( number at i should not be equal to number at i-1or number at i+1 index) to avoid iterating duplicate values

public int longestConsecutive(int[] nums) {
    int longestlength=1;
    int currentlength=1;
    if(nums.length==0)
        return 0;
    Arrays.sort(nums);
    for(int i=0;i<nums.length-1;i++){
        if(nums[i]!=nums[i+1]){
            if(nums[i+1]==nums[i]+1)
                currentlength+=1;
            else{
                longestlength=Math.max(currentlength,longestlength);
                currentlength=1;
            }
        }
    }
    return Math.max(longestlength,currentlength);
}

• This has a time complexity of O(nlogn) which is contributed due to sorting involved
• One more solution is to include a TreeSet that would insert elements in a sorted fashion and allow looping only in case of a subset entering
• For instance for an array {1,2,3,5,6,7,8}: traversal of elements after 1 would be taken into consideration and 2, 3 would be ignored but 5 will be considered and 6,7,8 reducing iterations
• This would have a time complexity of O(n) and extra space of O(n)

public int longestConsecutive(int[] nums) {
    Set<Integer> set=new TreeSet<Integer>();
    if(nums.length==0)
        return 0;
    int currentnum=0;
    int longestlength=1;
    int currentlength=1;
    for(int num: nums){
        set.add(num);
    }
    for(int num: set){
        if(!set.contains(num-1)){
            currentnum=num;
            currentlength=1;
            while(set.contains(currentnum+1)){
                currentlength+=1;
                currentnum=currentnum+1;
            }
            longestlength=Math.max(currentlength, longestlength);
        }
    }
    return longestlength;
}