MediumLeetCode #128Arrays & Hashing

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.

Constraints

0 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9

Examples

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

Output: 4

The longest consecutive sequence is [1, 2, 3, 4].

Solution

Approach

Use a HashSet for O(1) lookup. For each number, check if it is the start of a sequence (num-1 not in set), then count consecutive numbers.

def longestConsecutive(nums):
    num_set = set(nums)
    longest = 0
    for num in num_set:
        if num - 1 not in num_set:
            current = num
            streak = 1
            while current + 1 in num_set:
                current += 1
                streak += 1
            longest = max(longest, streak)
    return longest

Complexity

Time:O(n)

Space:O(n)

Hints

1.How do you identify the start of a sequence?
2.Use a set for O(1) lookups
3.Only start counting from sequence beginnings

Asked at

Google