Longest Consecutive Sequence

Description

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

Clarification:
Your algorithm should run in O(n) complexity.

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

Link

Lintcode_ladder

Method

1. Use hash set to record all numbers.
   Then, trying to expand from all possible number.
   As we can see, if the LCSeq is existed, any number in the seq will expand to the whole. Therefore, once we found one number can be expanded. We can simply erase() that entry, because we no logner need that. So the total complexity is still O(n)

2. x

Example

1. 1

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return an integer
     */
    int longestConsecutive(vector<int> &nums) {
        // write you code here
        if (nums.empty()) {
            return 0;
        }
        unordered_set<int> dict;
        int len = nums.size();
        int result = INT_MIN;
        // put nums into hash set
        for (int i = 0; i < len; ++i) {
            dict.insert(nums[i]);
        }
        // search in hash set
        // Because the consecutive sequence can be 1 or more
        // If we can find any part of the longest consecutive seq,
        // then, we can expand it to get the lognest one.
        // After that, we don't need to search the other part of longest seq again
        // So just erase it
        for (int i = 0; i < len; ++i) {
            int down = nums[i] - 1;
            while (dict.find(down) != dict.end()) {
                dict.erase(down);
                down--;
            }
            int up = nums[i] + 1;
            while (dict.find(up) != dict.end()) {
                dict.erase(up);
                up++;
            }
            result = max(result, up - down - 1);
        }
        return result;
    }
};

Similar problems

x

Tags

x