Longest Consecutive Sequence

[Longest Consecutive Sequence]

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

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

[Analysis]

In O(n) we can’t do a sort. Given O(n), what we can do is to scan through the array. Note that we also need to retain elements which are not sorted and thus not stored in order. We need to retrieve elements in order and it must be a O(1) operation to retrieve the “next” and the “previous” element of a given one. What comes to mind? Hashmap!


int longestConsecutive(vector<int> &num) {
        if (num.empty())
            return 0;
        unordered_set<int> hm;

        for (int i=0; i<num.size(); ++i) {
            hm.emplace(num[i]);
        }

        int max = 0;

        for (int e : num) {
            int c = 1;
            int left = e-1, right = e+1;

            while (hm.find(left)!=hm.end()) {
                c++;
                hm.erase(left);
                left--;
            }

            while (hm.find(right)!=hm.end()) {
                c++;
                hm.erase(right);
                right++;
            }

            max = std::max(c, max);
        }

        return max;
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s