128. Longest Consecutive Sequence

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

Your algorithm should run in O(n) complexity.

Example:

Input:
 [100, 4, 200, 1, 3, 2]

Output:
 4

Explanation:
 The longest consecutive elements sequence is 
[1, 2, 3, 4]
. Therefore its length is 4.

Solution

(1) Java

(2) Python

class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        myset = set(nums)
        rst = 0
        for num in nums:
            rst2 = 1
            num2 = num
            while num2+1 in myset:
                rst2 += 1
                num2 += 1
                myset.remove(num2)
            num2 = num
            while num2-1 in myset:
                rst2 += 1
                num2 -= 1
                myset.remove(num2)
            rst = max(rst, rst2)
        return rst

(3) Scala