DAY 6 - Longest Consecutive Sequence

Nayan Pahuja - Jun 9 '23 - - Dev Community

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-.6Looking forward to a positive interaction with all of you.

DAY 6 Problem 1: Longest Consecutive Sequence

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.

Intuition:

To find the longest consecutive sequence, we will need to get the elements in order.

Approach:1 Brute Force Approach

  • We can sort the array.
  • After sorting the array we can maintain a count for the longest sequence we can find.
  • In a case there is no sequence every number is a sequence in itself hence we return 1.

Code:

int longestConsecutive(vector<int>& nums) {
if(nums.size() == 0)
        {
            return 0;
        }
        if(nums.size() == 1)
        {
            return 1;
        }
sort(nums.begin(),nums.end());
        int ans = 1;
        int prev = nums[0];
        int cur = 1;

        for(int i = 1;i < nums.size();i++){
            if(nums[i] == prev+1){
                cur++;
            }
            else if(nums[i] != prev)
            {
                cur = 1;
            }
             prev = nums[i];
             ans = max(ans,cur);
        }
 return ans;
}
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Time Complexity: O(nlogn)
Space Complexity: O(1)

Approach 2: Optimal
We are going to take a hashSet which will basically store each value one time in an order eliminating any duplicates.
Following this we will check if the sequence's next element is available in the set. If it is, we will move to the next element.

Code:

int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0)
        {
            return 0;
        }
        if(nums.size() == 1)
        {
            return 1;
        }
        set<int> hashSet;
        int longestStreak = 0;
        for(int num: nums)
        {
            hashSet.insert(num);
        }
        for(int num: nums)
        {
            if(!hashSet.count(num-1))
            {
                int currentNum = num;
                int streak = 1;
                while (hashSet.count(currentNum + 1)) {
                    currentNum += 1;
                    streak += 1;
      }
            longestStreak = max(longestStreak,streak);
            }
        }
       return longestStreak; 
    }
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)
Assuming lookup for an element in hashSet is O(1).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .