11.Longest Consecutive Sequence

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

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4].
Therefore its length is 4.

Solution I: (Using Sorting)

class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {

        if (nums.size() == 0)
        {
            return 0;
        }

        sort(nums.begin(), nums.end());

        int start = 1;
        int m = INT_MIN;
        for (int i = 1; i < nums.size(); i++)
        {
            if (nums[i] != nums[i - 1])
            {
                if (nums[i] == nums[i - 1] + 1)
                {
                    start++;
                }
                else
                {
                    if (start > m)
                    {
                        m = start;
                    }
                    start = 1;
                }
            }
        }

        return max(m, start);
    }
};

Time Complexity: O(N log N) , Space Complexity: O(1)

Solution II: (Using set)

class Solution
{
public:
    int longestConsecutive(vector<int> &nums)
    {

        if (nums.size() == 0)
        {
            return 0;
        }

        set<int> s;

        for (int i = 0; i < nums.size(); i++)
        {
            s.insert(nums[i]);
        }

        int mx = INT_MIN;
        int count = 1;
        for (auto itr = s.begin(); itr != s.end(); itr++)
        {
            if (s.find(*itr - 1) == s.end())
            {
                if (count > mx)
                {
                    mx = count;
                }
                count = 1;
            }
            else
            {
                count++;
            }
        }

        return max(mx, count);
    }
};

Time Complexity: O(N) , Space Complexity: O(1)