LeetEye LeetEye
Easy Hash Set / Hash Map ~5 min

Longest Consecutive Sequence

arrays-and-hashing longest-consecutive-sequence

Problem

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.

Examples

Example 1
Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
The longest consecutive sequence is [1, 2, 3, 4]. Length = 4.
Example 2
Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
[0, 1, 2, 3, 4, 5, 6, 7, 8]. Length = 9.
Key Insight

Only start counting from sequence BEGINNINGS.

Only count from sequence starts (where num-1 doesn't exist). This ensures O(n) — each number is visited at most twice.

How to Approach This Problem

Pattern Recognition: When you see keywords like longest consecutive sequence arrays-and-hashing, think Hash Set / Hash Map.

Step-by-Step Reasoning

1 Sorting would make consecutive numbers adjacent. Why not use it?
Answer: Sorting is O(n log n), problem requires O(n)
Sorting works logically, but violates the O(n) time requirement.
2 To quickly check "does number X exist in the array?", use:
Answer: Hash set
Hash set gives O(1) average lookup. Convert array to set first.
3 If we try to extend a sequence from EVERY number:

nums = [1, 2, 3, 4]

Starting from 1: count 1→2→3→4, length 4
Starting from 2: count 2→3→4, length 3
Starting from 3: count 3→4, length 2
Starting from 4: count 4, length 1

What's wrong?
Answer: We're recounting overlapping sequences
Each number in the sequence triggers a partial recount. This gives O(n²) worst case.
4 How do we ensure each sequence is counted exactly once?
Answer: Only start counting if (num - 1) is NOT in the set
If num-1 exists, then num is not the start of its sequence — some earlier number will count it. Only true "sequence starts" trigger counting.
5 In nums = [100, 4, 200, 1, 3, 2], which numbers are sequence starts?
Answer: 100, 200, 1
1 is a start (0 not in set). 100 is a start (99 not in set). 200 is a start (199 not in set). 2, 3, 4 are NOT starts because their predecessors exist.
6 Starting from num = 1, how do we find the sequence length?
Answer: Check if 2, 3, 4, ... exist until one doesn't
From a start, extend right: does num+1 exist? Does num+2 exist? Count until you hit a gap.

Solution

def longestConsecutive(nums: List[int]) -> int:
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # Only start counting from sequence beginnings
        if num - 1 not in num_set:
            current = num
            length = 1
            
            while current + 1 in num_set:
                current += 1
                length += 1
            
            longest = max(longest, length)
    
    return longest

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Hash Set / Hash Map problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye