Longest Consecutive Sequence

Find the length of the longest consecutive elements sequence in an unsorted array.

Language Selection

Choose your preferred programming language

Showing: Python

Longest Consecutive Sequence

Problem Statement

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.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Approach 1: Hash Set (Optimal)

Algorithm

Use a hash set to store all numbers, then for each number, check if it’s the start of a sequence.

Steps:

  1. Add all numbers to a hash set
  2. For each number, check if it’s the start of a sequence (num-1 doesn’t exist)
  3. If it’s a start, count consecutive numbers
  4. Return the maximum count

Implementation

Python:

def longestConsecutive(nums):
    """
    Find longest consecutive sequence using hash set
    Time: O(n)
    Space: O(n)
    """
    if not nums:
        return 0
    
    num_set = set(nums)
    max_length = 0
    
    for num in num_set:
        # Check if this is the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_length = 1
            
            # Count consecutive numbers
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1
            
            max_length = max(max_length, current_length)
    
    return max_length

Java:

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int maxLength = 0;
        
        for (int num : numSet) {
            // Check if this is the start of a sequence
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                // Count consecutive numbers
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}

Go:

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }
    
    maxLength := 0
    
    for num := range numSet {
        // Check if this is the start of a sequence
        if !numSet[num-1] {
            currentNum := num
            currentLength := 1
            
            // Count consecutive numbers
            for numSet[currentNum+1] {
                currentNum++
                currentLength++
            }
            
            if currentLength > maxLength {
                maxLength = currentLength
            }
        }
    }
    
    return maxLength
}

JavaScript:

function longestConsecutive(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    const numSet = new Set(nums);
    let maxLength = 0;
    
    for (const num of numSet) {
        // Check if this is the start of a sequence
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLength = 1;
            
            // Count consecutive numbers
            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
    }
    
    return maxLength;
}

C#:

public class Solution {
    public int LongestConsecutive(int[] nums) {
        if (nums.Length == 0) {
            return 0;
        }
        
        var numSet = new HashSet<int>(nums);
        int maxLength = 0;
        
        foreach (int num in numSet) {
            // Check if this is the start of a sequence
            if (!numSet.Contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                // Count consecutive numbers
                while (numSet.Contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                maxLength = Math.Max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Each number is visited at most twice
  • Space Complexity: O(n) - For the hash set

Approach 2: Sorting

Algorithm

Sort the array and find the longest consecutive sequence.

Steps:

  1. Sort the array
  2. Remove duplicates
  3. Count consecutive sequences
  4. Return the maximum length

Implementation

Python:

def longestConsecutiveSorting(nums):
    """
    Find longest consecutive sequence using sorting
    Time: O(n log n)
    Space: O(1)
    """
    if not nums:
        return 0
    
    nums.sort()
    max_length = 1
    current_length = 1
    
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            continue  # Skip duplicates
        elif nums[i] == nums[i-1] + 1:
            current_length += 1
        else:
            max_length = max(max_length, current_length)
            current_length = 1
    
    return max(max_length, current_length)

Java:

class Solution {
    public int longestConsecutiveSorting(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        
        Arrays.sort(nums);
        int maxLength = 1;
        int currentLength = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                continue;  // Skip duplicates
            } else if (nums[i] == nums[i-1] + 1) {
                currentLength++;
            } else {
                maxLength = Math.max(maxLength, currentLength);
                currentLength = 1;
            }
        }
        
        return Math.max(maxLength, currentLength);
    }
}

Go:

func longestConsecutiveSorting(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    sort.Ints(nums)
    maxLength := 1
    currentLength := 1
    
    for i := 1; i < len(nums); i++ {
        if nums[i] == nums[i-1] {
            continue  // Skip duplicates
        } else if nums[i] == nums[i-1]+1 {
            currentLength++
        } else {
            if currentLength > maxLength {
                maxLength = currentLength
            }
            currentLength = 1
        }
    }
    
    if currentLength > maxLength {
        maxLength = currentLength
    }
    
    return maxLength
}

JavaScript:

function longestConsecutiveSorting(nums) {
    if (nums.length === 0) {
        return 0;
    }
    
    nums.sort((a, b) => a - b);
    let maxLength = 1;
    let currentLength = 1;
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i-1]) {
            continue;  // Skip duplicates
        } else if (nums[i] === nums[i-1] + 1) {
            currentLength++;
        } else {
            maxLength = Math.max(maxLength, currentLength);
            currentLength = 1;
        }
    }
    
    return Math.max(maxLength, currentLength);
}

C#:

public class Solution {
    public int LongestConsecutiveSorting(int[] nums) {
        if (nums.Length == 0) {
            return 0;
        }
        
        Array.Sort(nums);
        int maxLength = 1;
        int currentLength = 1;
        
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] == nums[i-1]) {
                continue;  // Skip duplicates
            } else if (nums[i] == nums[i-1] + 1) {
                currentLength++;
            } else {
                maxLength = Math.Max(maxLength, currentLength);
                currentLength = 1;
            }
        }
        
        return Math.Max(maxLength, currentLength);
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) due to sorting
  • Space Complexity: O(1) excluding the input array

Key Insights

  1. Hash Set Approach: Most efficient with O(n) time complexity
  2. Sequence Start Detection: Only count sequences starting from the beginning
  3. Duplicate Handling: Hash set automatically handles duplicates
  4. Sorting Alternative: Simpler but less efficient O(n log n) approach
  5. Edge Cases: Empty arrays and single elements need special handling

Edge Cases

  1. Empty Array: [] → 0
  2. Single Element: [1] → 1
  3. No Consecutive: [1,3,5] → 1
  4. All Same: [1,1,1] → 1
  5. Negative Numbers: [-1,0,1] → 3

Test Cases

def test_longest_consecutive():
    # Basic case
    assert longestConsecutive([100,4,200,1,3,2]) == 4
    
    # Multiple sequences
    assert longestConsecutive([0,3,7,2,5,8,4,6,0,1]) == 9
    
    # Empty array
    assert longestConsecutive([]) == 0
    
    # Single element
    assert longestConsecutive([1]) == 1
    
    # No consecutive
    assert longestConsecutive([1,3,5]) == 1
    
    # All same
    assert longestConsecutive([1,1,1]) == 1
    
    # Negative numbers
    assert longestConsecutive([-1,0,1]) == 3
    
    print("All tests passed!")

test_longest_consecutive()

Follow-up Questions

  1. Longest Increasing Subsequence: How would you find the longest increasing subsequence?
  2. Consecutive Sum: What if you need to find consecutive numbers that sum to a target?
  3. Multiple Sequences: How would you find all consecutive sequences?
  4. Circular Array: What if the array is circular?
  5. Streaming Data: How would you handle streaming data?

Common Mistakes

  1. Not Handling Duplicates: Forgetting that arrays can have duplicate numbers
  2. Wrong Sequence Start: Not checking if a number is the start of a sequence
  3. Sorting Side Effects: Modifying the original array when sorting
  4. Edge Cases: Not handling empty arrays or single elements

Interview Tips

  1. Clarify Requirements: Ask about duplicates and time complexity requirements
  2. Discuss Approaches: Mention both hash set and sorting approaches
  3. Optimize Time: Focus on the O(n) hash set solution
  4. Handle Edge Cases: Discuss empty arrays and single elements
  5. Explain Algorithm: Walk through the sequence detection logic

Variations

  1. Longest Increasing Subsequence: Find longest subsequence (not necessarily consecutive)
  2. Consecutive Sum: Find consecutive numbers that sum to a target
  3. Multiple Sequences: Find all consecutive sequences of length k
  4. Circular Array: Handle arrays where the sequence can wrap around
  5. Streaming Data: Handle data arriving one element at a time