[Top Interview 150 - Hashmap] 128. Longest Consecutive Sequence

[Q] [Medium]

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.

 

• 이 문제는 오름차순으로 하면 바로 풀릴 문제였지만, time complexity 로 인해 사용하기 어렵다.
• hash set 을 사용해야 한다.

# Answer

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:

        if not nums:
            return 0

        num_set = set(nums)
        max_length = 0

        for num in nums:
            if num - 1 not in num_set:
                current_num = num
                current_length = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1

                max_length = max(max_length, current_length)

        return max_length