Longest Consecutive Sequence | Problem No. 128 | LeetCode

Subscribe to my newsletter and never miss my upcoming articles

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

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

Constraints: 0 <= nums.length <= 104 -109 <= nums[i] <= 109

Follow up: Could you implement the O(n) solution?

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int longest=0;
        unordered_set<int>s(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++)
        {
            if(s.find(nums[i]-1)==s.end())
            {
                int cur = nums[i];
                int streak=1;
                while(s.find(cur+1)!=s.end())
                {
                    cur+=1;
                    streak++;
                }
                longest = max(longest,streak);
            }
        }
        return longest;
    }
}

No Comments Yet