Skip to main content

Longest Consecutive Sequence

Problem​

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.

Solution Approach​

Click - to see solution code
class Solution {
    map<int, int> mp, mp1;

   public:
    int findlongestConsecutive(int a) {
        if (mp1[a]) return mp1[a];
        if (mp[a] == 0) return 0;
        mp1[a] = 1;
        mp1[a] += findlongestConsecutive(a - 1);
        return mp1[a];
    }

    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            mp[nums[i]]++;
        }

        int ans = 0;
        for (auto i : mp) {
            ans = max(ans, findlongestConsecutive(i.first));
        }
        return ans;
    }
};