128. Longest Consecutive Sequence

Description

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.

Example 1:

• Input: nums = [100,4,200,1,3,2]
• Output: 4
• Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

• Input: nums = [100,4,200,1,3,2]
• Output: 4
• Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 3:

• Input: nums = [1,0,1,2]
• Output: 3

Constraints:

• 0 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹

Submitted Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)                        # 해시셋으로 변경
        max_len = 0

        for n in nums_set:
            if n-1 not in nums_set:                 # 해당 숫자가 연속 수열의 처음인지 확인
                curr_len = 1
                while n+1 in nums_set:
                    curr_len += 1
                    n += 1
                max_len = max(curr_len, max_len)

        return max_len

Runtime: 39 ms | Beats 94.78%
Memory: 36.63 MB | Beats 37.05%

𝑂(𝑛)의 시간 내에 해결하려면 해시셋을 사용해야 한다.

Other Solutions

1st

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numset = set(nums)
        longest = 0
        for n in numset:
            if n - 1 not in numset:
                length = 1
                while n + length in numset:
                    length += 1
                longest = max(longest, length)
        return longest

time complexity: 𝑂(𝑛)
space complexity: 𝑂(𝑛)