128. Longest Consecutive Sequence

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: nums = [100,4,200,1,3,2] Output: 4

Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9

Constraints: 0 <= nums.length <= 105 -109 <= nums[i] <= 109

Solution Approach

The solution uses a set to efficiently check for consecutive sequences by iterating through each number and extending the sequence while updating the maximum length found.

Algorithm

1. Utilize a Set: Store all numbers in a set for O(1) average-time complexity checks to quickly determine if consecutive numbers exist.
2. Identify Sequence Start: For each number, check if it is the start of a sequence by ensuring that n - 1 is not in the set.
3. Extend the Sequence: Once a sequence start is found, extend the sequence by checking if subsequent numbers (n + length) are in the set and keep track of the length of the longest sequence found.

Implement

    class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0

        for n in nums:
            if (n - 1) not in numSet:
                length = 0
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

    
    

Twitter  facebook  Email