Algorithm

LintCode/Longest Consecutive Sequence

Problem Summary

Given an unsorted array of integers, A[1], A[2],…, A[N], find the length of the longest consecutive elements sequence.

Solution 1

We can sort the array first, and iterate through it.

This takes O(NlogN) time but does not need extra space.

Solution 2

Unordered set or hash table can help us to achieve a better time complexity of O(N).

First, we put all integers in the array in an unordered set (or a hash table).

Second, we iterate through the given array. For each A[i], we calculate the maximal r such that A[i],A[i]+1,A[i]+2,…,A[i]+r are all in the set, the maximal l such that A[i],A[i]-1,A[i]-2,…,A[i]-l are all in the set. Then we update the answer with l+r+1, and erase A[i]-l,A[i]-l+1,…,A[i],A[i]+1,…,A[i]+r from the set.

The time and space complexity are both O(N).

Code for Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    /*
     * @param num: A list of integers
     * @return: An integer
     */
    int longestConsecutive(vector<int> &num) {
        unordered_set<int> s(num.begin(),num.end());
        int ans = 0;
        for (int i = 0; i < num.size(); ++i)
        {
        	if (!s.count(num[i]))
        		continue;
        	s.erase(num[i]);
        	int pre = num[i] - 1, next = num[i] + 1;
        	while (s.count(pre))
        		s.erase(pre--);
        	while (s.count(next))
        		s.erase(next++);
        	ans = max(ans,next - 1 - pre);
        }
        return ans;
    }
};