Longest Consecutive Sequence in C++ (O(n log n) Time Complexity)

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

For this lesson, your algorithm should run in O(n log n) time and use O(1) extra space.
(There are faster solutions which we will discuss in future lessons)

Problem Definition

The problem requires finding the length of the longest consecutive elements sequence in an unsorted array of integers.

Input:

• An unsorted array of integers.

Output:

• An integer representing the length of the longest consecutive elements sequence.

Constraints and Assumptions:

• The array can contain both positive and negative integers.
• The array can have duplicate elements.

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 integers in an unsorted array. This problem is significant in various applications such as data analysis, where identifying trends or patterns in data is crucial.

Potential pitfalls include handling duplicate elements and ensuring that the solution is efficient in terms of time complexity.

Approach

To solve this problem, we can start with a naive approach and then move to more optimized solutions.

Naive Solution:

The naive solution involves sorting the array and then finding the longest consecutive sequence. This approach is not optimal because sorting takes O(n log n) time, and we need to traverse the sorted array to find the sequence.

Optimized Solution:

We can use a set to achieve a more efficient solution. The idea is to use a set to store the elements of the array, and then iterate through the array to find the start of a sequence. For each start, we count the length of the sequence.

Steps:

1. Sort the array.
2. Initialize variables to keep track of the longest sequence.
3. Iterate through the sorted array and count the length of consecutive sequences.
4. Update the longest sequence length accordingly.

Algorithm

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

1. Sort the array.
2. Initialize a variable longestStreak to keep track of the longest sequence length.
3. Iterate through the sorted array and count the length of consecutive sequences.
4. Update longestStreak whenever a longer sequence is found.

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;

    sort(nums.begin(), nums.end());

    int longestStreak = 1;
    int currentStreak = 1;

    for (int i = 1; i < nums.size(); ++i) {
        if (nums[i] != nums[i - 1]) {
            if (nums[i] == nums[i - 1] + 1) {
                currentStreak += 1;
            } else {
                longestStreak = max(longestStreak, currentStreak);
                currentStreak = 1;
            }
        }
    }

    return max(longestStreak, currentStreak);
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << "Longest consecutive sequence length: " << longestConsecutive(nums) << endl;
    return 0;
}

Complexity Analysis

The time complexity of the above approach is O(n log n) due to the sorting step. The space complexity is O(1) as we are not using any extra space apart from a few variables.

Edge Cases

Potential edge cases include:

• Empty array: The output should be 0.
• Array with one element: The output should be 1.
• Array with all duplicate elements: The output should be 1.

Testing

To test the solution comprehensively, consider the following test cases:

• Simple cases with small arrays.
• Arrays with negative and positive integers.
• Arrays with duplicate elements.
• Large arrays to test performance.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem requirements and constraints thoroughly.
• Start with a naive solution and then optimize it.
• Use appropriate data structures to improve efficiency.
• Test your solution with various edge cases.

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 then optimized it using sorting. Understanding and solving such problems is crucial for developing strong problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode: Longest Consecutive Sequence
• GeeksforGeeks: Longest Consecutive Subsequence
• Coding Ninjas: Longest Consecutive Sequence