Course4all

Longest Consecutive Sequence

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Union-Find Perspective

If nums contains x and x+1, we can Union(x, x+1). The size of the largest component is the answer.
Medium

Examples

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

Level I: Sorting + HashSet

Intuition

Sort the array and then iterate through it, checking if the current number is exactly one greater than the previous one. A HashSet can also be used to query neighbors in O(1)O(1) time and expand sequences.
⏱ O(N log N) for sorting, or O(N) with HashSet.💾 O(N).
java
import java.util.*;
class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int n : nums) set.add(n);
        int max = 0;
        for (int n : set) {
            if (!set.contains(n - 1)) {
                int curr = n, count = 1;
                while (set.contains(curr + 1)) { curr++; count++; }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}
Approach 2

Level III: Union-Find (Set Growth)

Intuition

Iterate through each number num. If num+1 exists in the set, union num and num+1. Keep track of the size of each component.
⏱ O(N \cdot \alpha(N)).💾 O(N).
java
import java.util.*;
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0) return 0;
        Map<Integer, Integer> p = new HashMap<>(), sz = new HashMap<>();
        for(int n : nums) { p.put(n, n); sz.put(n, 1); }
        int max = 1;
        for(int n : nums) {
            if(p.containsKey(n + 1)) {
                int r1 = find(p, n), r2 = find(p, n + 1);
                if(r1 != r2) { p.put(r1, r2); sz.put(r2, sz.get(r2) + sz.get(r1)); max = Math.max(max, sz.get(r2)); }
            }
        }
        return max;
    }
    int find(Map<Integer, Integer> p, int i) { if(p.get(i)==i) return i; p.put(i, find(p, p.get(i))); return p.get(i); }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionRemove Max Number of Edges to Keep Graph Fully Traversable
Next Question →Couples Holding Hands