Start learning free

LESSON 301 OF 667 · SORTING

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

Practice O(n log n) Read the full explanation

You get a vector nums of integers, in no particular order.

Return the length of the longest run of consecutive values.

Consecutive values go up by 1 each time. For example, 5, 6 and 7 form a run of length 3.

The values of a run can be anywhere in nums. A value that appears more than once counts only once.

Example 1:

Input: nums = [9, 13, 10, 5, 11, 6]
Output: 3
Explanation: 9, 10 and 11 make the longest run.
5 and 6 make a shorter run.
13 stands alone.

Example 2:

Input: nums = [-2, 0, -1, 0, 2, -1]
Output: 3
Explanation: The longest run is -2, -1 and 0.
0 and -1 appear twice, but each counts once.
2 is not in the run, because 1 is missing.

Example 3:

Input: nums = [40, 10, 30, 20]
Output: 1
Explanation: No two values are 1 apart.
So every run has just one value.

Constraints:

  • nums has 1 to 30,000 integers.
  • Each value is from -100 to 100,000,000.

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++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free