Course4all
Join us on telegram
Home/dsa/Union Find/Longest Consecutive Sequence

Longest Consecutive Sequence

Master this topic with zero to advance depth.

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); }
}
← Previous QuestionRemove Max Number of Edges to Keep Graph Fully Traversable
Next Question →Couples Holding Hands