Skip to content

Leetcode 128 - Longest Consecutive Sequence

Difficulty: medium

Table of contents

Open Table of contents


Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. The algorithm should run in O(n) time complexity.

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 = [0,3,7,2,5,8,4,6,0,1]
Output: 9



To solve this problem efficiently, we use a hash set to store all elements of the array. Then, for each element, we check if it’s the start of a sequence and calculate the length of this sequence.

Hash Set Approach:

Solution: Hash Set

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

        for num in num_set:
            # Check if it's the start of a sequence
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # Count the length of the sequence
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

Time and Memory Complexity

The time complexity is O(n), assuming a good hash function with O(1) average lookup time. Each element is processed once, and the inner while loop runs for consecutive sequences, which doesn’t exceed the total number of elements. The space complexity is O(n) to store the hash set.


The algorithm first inserts all elements into a hash set. Then, it iterates through the set, checking if each number is the start of a new sequence. It then counts the length of the sequence and updates the maximum length found.

Visual Representation

Consider the input nums = [100, 4, 200, 1, 3, 2].

  1. Hash Set Creation:

    • The hash set contains all unique elements of nums.
    • Set: {100, 1, 2, 3, 4, 200}.
  2. Identifying Sequences:

    • Start at 100: It’s the first sequence
    • Since 101 is not in set, longest_streak = 1
    • At 1: Starts a sequence. Sequence is [1, 2, 3, 4] with length 4.
    • Other elements are part of this already identified sequence.
  3. Result:

    • The longest consecutive sequence identified is [1, 2, 3, 4].
    • The length of this sequence is 4.