128. Longest Consecutive Sequence

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.

Examples

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
Explanation: The longest consecutive elements sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Therefore its length is 9.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def longestConsecutive(nums: List[int]) -> int:
    if not nums:
        return 0
    
    # Create a set for O(1) lookup
    num_set = set(nums)
    longest = 0
    
    for num in num_set:
        # Only check sequences from their smallest number
        if num - 1 not in num_set:
            current = num
            current_streak = 1
            
            # Count consecutive numbers
            while current + 1 in num_set:
                current += 1
                current_streak += 1
            
            longest = max(longest, current_streak)
    
    return longest

Java Solution


class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        // Create a set for O(1) lookup
        Set numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longest = 0;
        
        for (int num : numSet) {
            // Only check sequences from their smallest number
            if (!numSet.contains(num - 1)) {
                int current = num;
                int currentStreak = 1;
                
                // Count consecutive numbers
                while (numSet.contains(current + 1)) {
                    current++;
                    currentStreak++;
                }
                
                longest = Math.max(longest, currentStreak);
            }
        }
        
        return longest;
    }
}

C++ Solution


class Solution {
public:
    int longestConsecutive(vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        
        // Create a set for O(1) lookup
        unordered_set numSet(nums.begin(), nums.end());
        int longest = 0;
        
        for (int num : numSet) {
            // Only check sequences from their smallest number
            if (!numSet.count(num - 1)) {
                int current = num;
                int currentStreak = 1;
                
                // Count consecutive numbers
                while (numSet.count(current + 1)) {
                    current++;
                    currentStreak++;
                }
                
                longest = max(longest, currentStreak);
            }
        }
        
        return longest;
    }
};

JavaScript Solution


/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if (!nums.length) {
        return 0;
    }
    
    // Create a set for O(1) lookup
    const numSet = new Set(nums);
    let longest = 0;
    
    for (const num of numSet) {
        // Only check sequences from their smallest number
        if (!numSet.has(num - 1)) {
            let current = num;
            let currentStreak = 1;
            
            // Count consecutive numbers
            while (numSet.has(current + 1)) {
                current++;
                currentStreak++;
            }
            
            longest = Math.max(longest, currentStreak);
        }
    }
    
    return longest;
};

C# Solution


public class Solution {
    public int LongestConsecutive(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }
        
        // Create a set for O(1) lookup
        HashSet numSet = new HashSet(nums);
        int longest = 0;
        
        foreach (int num in numSet) {
            // Only check sequences from their smallest number
            if (!numSet.Contains(num - 1)) {
                int current = num;
                int currentStreak = 1;
                
                // Count consecutive numbers
                while (numSet.Contains(current + 1)) {
                    current++;
                    currentStreak++;
                }
                
                longest = Math.Max(longest, currentStreak);
            }
        }
        
        return longest;
    }
}

Complexity Analysis

Solution Explanation

This solution uses a hash set approach:

Key points: