128. Longest Consecutive Sequence

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

You must write an algorithm that runs in O(n) time.

def longestConsecutive_O_N(self, nums: List[int]):

       

    longest = 0

    numSet = set(nums)

   

    for n in nums:

        if n - 1 not in numSet:

            curNum = n                

            curStreak = 1

           

            while curNum + 1 in numSet:

                curNum += 1

                curStreak += 1

               

            longest = max(longest, curStreak)            

        return longest

   

def longestConsecutiveMyOldAlgo(nums):

    s = set(nums)

    max_len = 0

    explored = set()

    for n in nums:      

        if n in explored:

            continue

        seq_len = 1

        # traverse left

        p = n - 1

        while p in s:

            explored.add(p)

            p -= 1

            seq_len += 1

        # traverse right

        p = n + 1

        while p in s:

            explored.add(p)

            p += 1

            seq_len += 1        

        max_len = max(max_len, seq_len)

    return max_len