Longest consecutive sequence

Array Hash Table Union-Find

47.0% acceptance

Jan 12, 2026

22741

1228

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
    use std::collections::HashSet;
    
    let num_set: HashSet<i32> = nums.into_iter().collect();
    let mut max_len = 0;
    
    for &num in &num_set {
      if !num_set.contains(&(num - 1)) {
        let mut current = num;
        let mut len = 1;
        
        while num_set.contains(&(current + 1)) {
          current += 1;
          len += 1;
        }
        
        max_len = max_len.max(len);
      }
    }
    
    max_len
  }
}