Longest Consecutive Sequence

 Longest Consecutive Sequence

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

Your algorithm should run in O(n) complexity.

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.

class Solution {

public:

    int longestConsecutive(vector<int>& nums) {

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

        map<int,int> mp;

        for(int i=0;i<nums.size();++i)

        {

            mp[nums[i]]++;

        }

        int cnt=1,ans=1;

        vector<int> v;

        for(auto p=mp.begin();p!=mp.end();++p)

        {

          v.push_back(p->first);

        }

        for(int i=0;i<v.size()-1;++i)

        {

            if(v[i]+1==(v[i+1]))

            {

                ++cnt;

            }else{

                ans=max(ans,cnt);

                cnt=1;

            }

        }

        ans=max(ans,cnt);

        return ans;

    }

};

--------------------------------------------------------------------------------------------------------------------------

class Solution {

    public int longestConsecutive(int[] nums) {

        Set<Integer> num_set = new HashSet<Integer>();

        for (int num : nums) {

            num_set.add(num);

        }

        int longestStreak = 0;

        for (int num : num_set) {

            if (!num_set.contains(num-1)) {

                int currentNum = num;

                int currentStreak = 1;

                while (num_set.contains(currentNum+1)) {

                    currentNum += 1;

                    currentStreak += 1;

                }

                longestStreak = Math.max(longestStreak, currentStreak);

            }

        }

        return longestStreak;

    }

}

-----------------------------------------------------------------------------------------------------------------------

class Solution:

    def longestConsecutive(self, nums):

        longest_streak = 0

        num_set = set(nums)

        for num in num_set:

            if num - 1 not in num_set:

                current_num = num

                current_streak = 1

                while current_num + 1 in num_set:

                    current_num += 1

                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak