Longest Consecutive Sequence

• [leetcode ]
• Hard
• Company Tag: Google, Facebook
• Tags: Array, Union Find
• Similar Problems: Binary Tree Longest Consecutive Sequence

Description

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.

Previous Thinking

I would like to give a banch of solutions of this problem, Each relative later solution is optimized based on the previous one. Then I want to summarized the usage of Set briefly.

C++ Solution 1

This solution is given in SoulMachine

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //this version use unordered_map<int,bool> used;
        unordered_map<int,bool> used;
        //initialization
        for(auto i :nums){
            used[i] = false;
        }

        int longest = 0;

        for(auto i : nums){
            if(used[i]) continue;

            int length = 1;

            used[i] = true;

            for(int j = i + 1; used.find(j) != used.end(); ++j){
                used[j] = true;
                ++length;
            }

            for(int j = i - 1; used.find(j) != used.end() ; --j){
                used[j] = true;
                ++length;
            }

            longest = max(longest, length);
        }

        return longest;
    }
};

We can use unordered_set<int> to replace the unordered_map<int, bool>.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //this version use unordered_map<int,bool> used;
        unordered_set<int> used;
        //initialization
        for(auto i :nums){
            used.insert(i);
        }

        int longest = 1;

        for(auto i : nums){
            if(used.find(i) == used.end()) continue;

            used.erase(i);
            int length = 1;

            for(int j = i + 1; used.find(j) != used.end(); ++j){
                used.erase(j);
                ++length;
            }

            for(int j = i - 1; used.find(j) != used.end() ; --j){
                used.erase(j);
                ++length;
            }

            longest = max(longest, length);
        }

        return longest;
    }
};

if we just start to increase the length at the beginning of the smallest number of a range. We can reduce a for-loop. However, it is just a trick. No real upgrade in performance showed up in comparison.

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //this version use unordered_map<int,bool> used;
        unordered_set<int> used;
        //initialization
        for(auto i :nums){
            used.insert(i);
        }

        int longest = 1;

        for(auto i : nums){
            if(used.find(i - 1) == used.end()){
                used.erase(i);
                int length = 1;

                for(int j = i + 1; used.find(j) != used.end(); ++j){
                    used.erase(j);
                    ++length;
                }
                longest = max(longest, length);
            }
        }
        return longest;
    }
};

Java Solution

This solution is based on the last version of c++ solutions.

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();

        for(int i : nums) set.add(i);

        int longest = 1;

        for(int i : nums){
            if(!set.contains(i - 1)){
                int length = 0;
                int val = i;
                while(set.remove(val++)) length++;
                longest = Math.max(longest,length);
            }
        }

        return longest;
    }
}

Another Way

We can use a hashMap to maintain the length of the range each number lying in. The structure of the code is more similar to Union Find.

C++ Solution

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int> map;
        int size=nums.size();

        int l=1;

        for(int i=0;i<size;i++){
            if(map.find(nums[i])!=map.end()) continue;
            map[nums[i]]=1;

            if(map.find(nums[i]-1)!=map.end()){
                l=max(l,merge(map,nums[i]-1,nums[i]));
            }

            if(map.find(nums[i]+1)!=map.end()){
                l=max(l,merge(map,nums[i],nums[i]+1));
            }
        }

        return l;
    }

    private:
        int merge(unordered_map<int,int>& map, int left,int right){
            int upper=right+map[right]-1;
            int lower=left-map[left]+1;
            int length=upper-lower+1;
            map[upper]=length;
            map[lower]=length;
            return length;
        }
};

Notice

in this solution, we can just make sure the two end of each range is correct finally.