Longest Consecutive Sequence II in C++ (O(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

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

Understanding the Problem

The core challenge of this problem is to find the longest sequence of consecutive integers 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 result in a time complexity of O(n log n), not meeting the O(n) requirement.

Approach

To solve this problem efficiently, we can use a hash set to achieve O(n) time complexity. The idea is to use the set to quickly check the existence of elements and build the longest sequence.

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 hash set to store the elements of the array. We then 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 count the length of the sequence by checking the presence of consecutive elements in the set.

Algorithm

1. Create a hash set and add all elements of the array to it.
2. Initialize a variable to keep track of the maximum sequence length.
3. Iterate through the array, and for each element, check if it is the start of a sequence.
4. If it is the start, 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

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longestStreak = 0;

    for (int num : nums) {
        // Check if it's the start of a sequence
        if (numSet.find(num - 1) == numSet.end()) {
            int currentNum = num;
            int currentStreak = 1;

            // Count the length of the sequence
            while (numSet.find(currentNum + 1) != numSet.end()) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

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 this approach is O(n) because each element is processed at most twice (once when added to the set and once when checking for sequences). The space complexity is also O(n) due to the storage of elements in the hash set.

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 elements the same: The output should be 1.

These cases are handled naturally by the algorithm as it checks for the presence of elements in the set.

Testing

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

• Simple cases with small arrays.
• Arrays with negative numbers.
• Arrays with duplicate elements.
• Large arrays to test performance.

Thinking and Problem-Solving Tips

When approaching such problems, it's essential to:

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

Conclusion

In this blog post, we discussed how to find the longest consecutive sequence in an unsorted array using an efficient O(n) time complexity algorithm. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

Additional Resources

For further reading and practice, consider the following resources:

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