Start learning free

LESSON 222 OF 410 · SORTING

Longest Consecutive Sequence in O(n log n) Time Using Python

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 len(nums)).
  • 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

    PYTHON · SORTING

    Longest Consecutive Sequence in Python, explained

    Problem Definition

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

    • Input: An unsorted array of integers.
    • Output: The length of the longest consecutive elements sequence.
    • Constraints: The algorithm should run in O(n log n) time and use O(1) extra space.

    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. A common pitfall is to assume that sorting the array and then finding the sequence is the only way, but there are more efficient methods.

    Approach

    To solve this problem, we can start with a naive approach and then optimize it:

    Naive Solution

    The naive solution involves sorting the array and then finding the longest consecutive sequence. This approach is straightforward but not optimal in terms of time complexity.

    Optimized Solution

    We can optimize the solution by using a set to keep track of the elements and then iterate through the array to find the longest sequence. This approach ensures that we only traverse the array once, achieving O(n) time complexity.

    Algorithm

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

    1. Sort the array.
    2. Initialize variables to keep track of the longest sequence and the current sequence length.
    3. Iterate through the sorted array and check if the current element is consecutive to the previous element.
    4. If it is consecutive, increment the current sequence length.
    5. If it is not consecutive, update the longest sequence length if the current sequence is longer, and reset the current sequence length.
    6. Return the longest sequence length.

    Code Implementation

    def longest_consecutive(nums):
    # Sort the array
    nums.sort()
    
    # Initialize variables
    longest_streak = 0
    current_streak = 1
    
    # Iterate through the sorted array
    for i in range(1, len(nums)):
        # Check if the current element is consecutive to the previous element
        if nums[i] != nums[i - 1]:  # Skip duplicates
            if nums[i] == nums[i - 1] + 1:
                current_streak += 1
            else:
                longest_streak = max(longest_streak, current_streak)
                current_streak = 1
    
    # Return the longest sequence length
    return max(longest_streak, current_streak)

# Example usage
print(longest_consecutive([100, 4, 200, 1, 3, 2]))  # Output: 4
print(longest_consecutive([0, 2, 0, 1, 2, 3, 1]))  # Output: 4

    Complexity Analysis

    The time complexity of the optimized solution 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 elements the same: The output should be 1.

    Testing

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

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

    Thinking and Problem-Solving Tips

    When approaching such problems, it is essential to:

    • Understand the problem requirements and constraints.
    • Start with a naive solution and then optimize it.
    • Consider edge cases and test the solution thoroughly.

    Conclusion

    In this blog post, we discussed how to find the longest consecutive sequence in an unsorted array of integers. We explored a naive solution and then optimized it to achieve O(n log n) time complexity. Understanding and solving such problems is crucial for developing problem-solving skills and improving algorithmic thinking.

    Additional Resources

    For further reading and practice, consider the following resources:

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