Longest Consecutive Sequence

LeetCode 128 | Difficulty: Medium

Medium

Problem Description

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.

Example 2:

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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

- `0 <= nums.length <= 10^5`

- `-10^9 <= nums[i] <= 10^9`

Topics: Array, Hash Table, Union-Find

---

Approach

Union-Find

Maintain disjoint sets with two operations: find (which set does element belong to?) and union (merge two sets). Use path compression and union by rank for near O(1) amortized operations.

When to use

Connected components, cycle detection in undirected graphs, grouping elements.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	23.3 MB
Date	2019-02-18

Solution

public class Solution {
    public int LongestConsecutive(int[] nums)
{
    HashSet<int> h = new HashSet<int>();
    int max = 0;
    foreach (var n in nums)
    {
        h.Add(n);
    }
    
    foreach (var x in h)
    {
        if(!h.Contains(x-1))
        {
            int y = x+1;
            while(h.Contains(y))
            {
                y++;
            }
            max = Math.Max(max, y-x);
        }
    }
    
    return max;
    
}
}

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$
Union-Find	$O(n × α(n))$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.