Longest Consecutive Sequence Solution


  • 0
    H

    Brute force Solution [Accepted]
    Sort the given array into ascending or descending order. Then scan the array once to find the longest consecutive sequence. The time complexity of this solution is O(nlogn), but the space complexity is O(1).

    public int longestConsecutive(int[] nums) {
            /* Sorting : Sort the array and find the longest subarray 
            by counting consecutive element. It will not work for 
            duplicates in the array.
            TC : O(nlog n)
            SC : O(1)
            */
            
            // if the array is null just return
            if(nums.length == 0)
                return 0;
            
            // sort the array
            Arrays.sort(nums);
            int count = 1;
            int res = 1;
            
            for(int i=0; i<nums.length - 1; i++){
                System.out.println(nums[i]);
                if (nums[i] == nums[i+1]){
                    continue; // for duplicates skip the next element
                }
                if(i<nums.length -1){
                    if(nums[i]+1 == nums[i+1] ){
                    count++;
                    res = Math.max(res,count);
                } 
                else
                    count = 1;
                } // end of if
                
            } // end of for loop
            return res;
        } // method
    

    Efficient Solution using HashSet[Accepted]
    We can design a O(n) solution using O(n) space complexity by creating a HashSet.

    public int longestConsecutive(int[] nums) {
            /* Using HashSet to store the distinct elements of the given array in the set.
            We do not need HashMap becuase index is of no importance.
            Then seaarch for the vales after num[i], since it is the first element in the sequence.
            TC : O(n)
            SC : O(n)
            */
            
            Set<Integer> lookup = new HashSet<Integer>();
            
            for(int i =0; i<nums.length; i++)
                lookup.add(nums[i]);
            
            int res =0; // stores the length of solution
            for(int i =0; i<nums.length; i++){
                if(!lookup.contains(nums[i]-1)){
                    int j = nums[i];
                     while(lookup.contains(j))
                        j++;
                    if(res < j-nums[i])
                      res = j-nums[i]; // since j is ahead of i always.
                } // end of if
            }// end of for 
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.