Longest Consecutive Sequence II in O(n) Time Complexity using JavaScript

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
             Therefore its length is 4.

Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
             Therefore its length is 4.
	     Note that we count each value once, even tho values 0, 1 and 2 appear 2 times each in nums

Your algorithm should run in O(n) time and use O(n) extra space.

Problem Definition

The problem requires finding the length of the longest consecutive sequence in an unsorted array of integers. The input is an array of integers, and the output is a single integer representing the length of the longest consecutive sequence.

Input:

Array of integers, e.g., [100, 4, 200, 1, 3, 2]

Output:

Single integer, e.g., 4

Constraints and Assumptions:

• The array can contain duplicates.
• The array can contain both positive and negative integers.
• The solution should run in O(n) time complexity and use O(n) extra space.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.

Understanding the Problem

The core challenge is to identify the longest sequence of consecutive numbers in an unsorted array. This problem is significant in various applications such as data analysis, where finding patterns in data is crucial. A common pitfall is to sort the array first, which would not meet the O(n) time complexity requirement.

Approach

To solve this problem efficiently, we can use a set to store the elements of the array. This allows for O(1) average time complexity for lookups. The idea is to iterate through the array and for each element, check if it is the start of a sequence (i.e., the previous element is not in the set). If it is, we then count the length of the sequence starting from that element.

Naive Solution:

A naive solution would involve sorting the array and then finding the longest consecutive sequence. However, this approach has a time complexity of O(n log n) due to the sorting step, which is not optimal.

Optimized Solution:

The optimized solution involves using a set to store the elements of the array. This allows us to check for the presence of elements in O(1) time. We then iterate through the array and for each element, check if it is the start of a sequence. If it is, we count the length of the sequence.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Create a set from the array elements for O(1) lookups.
2. Initialize a variable to keep track of the maximum sequence length.
3. Iterate through the array. For each element, check if it is the start of a sequence (i.e., the previous element is not in the set).
4. If it is the start of a sequence, count the length of the sequence by checking the presence of consecutive elements in the set.
5. Update the maximum sequence length if the current sequence is longer.

Code Implementation

// Function to find the length of the longest consecutive sequence
function longestConsecutive(nums) {
    // Create a set from the array elements
    const numSet = new Set(nums);
    let maxLength = 0;

    // Iterate through the array
    for (let num of nums) {
        // Check if the current number is the start of a sequence
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLength = 1;

            // Count the length of the sequence
            while (numSet.has(currentNum + 1)) {
                currentNum += 1;
                currentLength += 1;
            }

            // Update the maximum sequence length
            maxLength = Math.max(maxLength, currentLength);
        }
    }

    return maxLength;
}

// Example usage
console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // Output: 4
console.log(longestConsecutive([0, 2, 0, 1, 2, 3, 1])); // Output: 4

Complexity Analysis

The time complexity of this solution is O(n) because we iterate through the array once and perform O(1) operations for each element. The space complexity is also O(n) due to the set used to store the array elements.

Edge Cases

Potential edge cases include:

• An empty array: The output should be 0.
• An array with one element: The output should be 1.
• An array with all elements the same: The output should be 1.

These edge cases can be tested as follows:

console.log(longestConsecutive([])); // Output: 0
console.log(longestConsecutive([1])); // Output: 1
console.log(longestConsecutive([2, 2, 2])); // Output: 1

Testing

To test the solution comprehensively, include a variety of test cases:

• Simple cases with small arrays.
• Cases with negative numbers.
• Cases with large arrays to test performance.

Example test cases:

console.log(longestConsecutive([1, 2, 0, 1])); // Output: 3
console.log(longestConsecutive([-1, -2, -3, -4])); // Output: 4
console.log(longestConsecutive([10, 5, 12, 3, 55, 30, 4, 11, 2])); // Output: 4

Thinking and Problem-Solving Tips

When approaching such problems:

• Understand the problem requirements and constraints thoroughly.
• Consider different approaches and their time complexities.
• Use data structures that provide efficient operations for the problem at hand.
• Practice solving similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to find the length of the longest consecutive sequence in an unsorted array of integers. We explored a naive solution and an optimized solution using a set for O(1) lookups. We also provided a detailed algorithm, code implementation, complexity analysis, and testing strategies. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice problems, consider the following resources:

• LeetCode: Longest Consecutive Sequence
• GeeksforGeeks: Longest Consecutive Subsequence
• HackerRank: Longest Consecutive Sequence