128.Longest Consecutive Sequence

Tags: [set], [trick]

Com: {fb}

Link: https://leetcode.com/problems/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.

Solution: Set, Trick

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        nums_set = set(nums)
        max_len = 0
        for num in nums:
            if num - 1 not in nums_set:
                # num is the start of one of sequences.
                next = num + 1
                while next in nums_set:
                    next += 1
                max_len = max(max_len, next - num)

        return max_len

Revelation:

• Think about there are multiple sequences. we just need to find out the start of the sequence, and because we want to find the 'consecutive sequence', so once we find the start, we can just check start + 1, start + 2, start + 3, ... in the nums_set or not to build out each sequence.

Note:

• Time complexity = O(n), n is the number of elements of the given array. Because each sequence we just visited once, and the number of elements of all sequences == all elements we have.