Start learning free

LESSON 221 OF 409 · SORTING

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

Practice O(n log n) Read the full explanation

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Example 1:

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

Example 2:

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 though values 0, 1 and 2 appear 2 times each in nums

Note:

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)


Hints:

Let's sort the array in non-decreasing order. In this way each consecutive elements sequence is a subarray of the sorted array. Even more, these consecutive elements subarrays will come one after another.

Let's start by finding the first subarray. Its left endpoint is i = 0. We will use another index variable j to find the right endpoint. j is initially equal to i + 1 and should be incremented for as long as nums[i...j] is a consecutive subarray. But how can we check this?

j is initially equal to i + 1 and will be incremented as long as nums[j] <= nums[j - 1] + 1. When the condition is not satisfied anymore, we have found the first subarray: nums[i...j-1]. How can we find the second one?

The left endpoint of the second subarray is j. So we can set the index i to j. Then we can continuously increment j as long as our condition is satisfied just like we did for the first subarray. When the condition is not satisfied anymore, we have found the second subarray: nums[i...j-1]. Can we use the same strategy for finding the rest of the subarrays?

Yes, we can. We should design an algorithm that repeats this strategy until we are left with no more subarrays (e.g. i >= n, where n is nums.size()).
  • 1. Initialize i with 0.
  • 2. While i < n:
    • 1. Initialize j with i + 1.
    • 2. While nums[j] <= nums[j - 1] + 1, increment j
    • 3. Set i to j and return to step 1.

STEP 1 OF 11
    Ctrl + Enter to check

    C++ · SORTING

    Longest Consecutive Sequence in C++, explained

    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:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free