Gowthaman Ravi
Gowthy's Blog

Gowthy's Blog

Longest Consecutive Sequence | Problem No. 128 | LeetCode

Gowthaman Ravi's photo
Gowthaman Ravi
·Feb 22, 2021·

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;
    }
}
 
Share this