Longest Consecutive Sequence

Medium Subject: Arrays & Hashing

Time Complexity

O(N)

Space Complexity

O(N)

Problem Description

Problem Statement

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.

Optimal Solution

Python

Approach: Hash Set

We add all numbers to a set. Then, we iterate through the set. If num - 1 is not in the set, it means num is the start of a sequence. We then count upwards (num + 1, num + 2, etc.) to find the length of this sequence.

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

        for n in num_set:
            if (n - 1) not in num_set:
                length = 1
                while (n + length) in num_set:
                    length += 1
                longest = max(longest, length)

        return longest