128. Longest Consecutive Sequence

Problem Statement

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. (link)

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

Solution

Brute force Approach (Using Sort)

Begin by sorting the array. Next, determine if the last smaller element is consecutive to the current one. If it is, increment the count; otherwise, initiate a new count. It's important to note that if the current element is identical to the last smaller element, no action is taken. Always compare the count with the global maximum and update the global max variable with the maximum value.

Time Complexity - O(nlogn)

Space Complexity - O(1)

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<=1) return nums.length;

        int ans = 1;

        Arrays.sort(nums);

        int lastSmall = nums[0];
        int count = 1;
        for(int i=1; i<nums.length; i++){
            if(lastSmall+1==nums[i]){
                count+=1;
                lastSmall = nums[i];
            } else if(lastSmall!=nums[i]){
                lastSmall = nums[i];
                count=1;
            }
            ans = Math.max(ans,count);
        }
        return ans;
    }
}

Optimal Approach

Ensure that all elements are placed within a set. Subsequently, focus on consecutive elements exclusively for the minimum number. Given that the minimum number won't have any preceding numbers, initiate the process from the minimum value and tally the count of consecutive elements. Maintain a global count, updating it with the maximum count observed thus far.

Time Complexity - O(n)

Space Complexity - O(n)

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length<=1) return nums.length;
        Set<Integer> set = new HashSet<>();

        for(int num: nums){
            set.add(num);
        }

        int ans = 1;
        for(int num: set){
            if(!set.contains(num-1)){
                int count = 0;
                while(set.contains(num)){
                    count+=1;
                    num+=1;
                }
                ans = Math.max(ans, count);
            }
        }
        return ans;
    }
}