128. Longest Consecutive Sequence#

Difficulty: Medium

Link to Problem: To see the Longest Consecutive Sequence problem on LeetCode, click here!

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

You must write an algorithm that runs in O(n) time.

Constraints:*

  • 0 <= nums.length <= \(10^5\)

  • \(-10^9\) <= nums[i] <= \(10^9\)

Solution:#

Here’s a Python function to solve this problem:

def longestConsecutive(nums):
    if not nums:
        return 0

    num_set = set(nums)
    max_length = 0

    for num in num_set:
        if num - 1 not in num_set:
            current_num = num
            current_length = 1

            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1

            max_length = max(max_length, current_length)

    return max_length

Explanation:#

  1. We start by defining the longestConsecutive function that takes the nums array as input.

  2. We check if the nums array is empty. If it’s empty, there are no consecutive elements, so we return 0.

  3. We create a Python set called num_set and insert all elements from the nums array into it. Using a set allows us to efficiently check for the existence of elements in O(1) time.

  4. We initialize a variable max_length to 0. This variable will keep track of the maximum length of consecutive elements sequence found.

  5. We iterate through the elements of the num_set. For each element num, we check if num - 1 exists in the num_set. If it doesn’t exist, it means num is the starting element of a potential consecutive sequence.

  6. Inside the loop, we initialize two variables: current_num to the current element num and current_length to 1. We start with a length of 1 because num itself is part of the sequence.

  7. We then enter a while loop that continues as long as current_num + 1 exists in the num_set. This means we are incrementing the consecutive sequence.

  8. Inside the while loop, we increment current_num by 1 and also increment current_length by 1 to account for the next consecutive element.

  9. We compare current_length with the max_length and update max_length if the current sequence is longer.

  10. After the while loop, we move to the next element in the outer loop and repeat the process.

  11. Finally, we return the max_length as the result, which represents the length of the longest consecutive elements sequence in the nums array.

The key idea here is to use a set to efficiently check for the existence of elements and to iterate through the elements, considering each element as the potential start of a consecutive sequence. By doing this, we can find the longest consecutive sequence in O(n) time complexity, where n is the number of elements in the array.

Test cases#

# Example 1: 

nums1 = [100, 4, 200, 1, 3, 2]
print(longestConsecutive(nums1))

4

# Example 2:

nums2 = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
print(longestConsecutive(nums2)) 

9

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity: The code is designed to run in O(n) time complexity, where n is the number of elements in the nums array. Here’s the breakdown:

  1. Constructing the num_set by inserting all elements from nums into it takes O(n) time because we perform an insertion operation for each element in nums.

  2. The main loop iterates through the elements in num_set. In the worst case, each element is visited only once, so the loop itself takes O(n) time.

  3. Within the loop, we have a while loop that may also take O(n) time in the worst case. However, this while loop is nested inside the main loop, so its overall time complexity remains O(n).

Therefore, the overall time complexity of the code is O(n).

Space Complexity: The space complexity of the code is determined by the space used by the num_set and a few additional variables. Here’s the breakdown:

  1. num_set is a set that stores the unique elements from nums. In the worst case, it can store all n elements from nums, so the space complexity is O(n).

  2. The additional variables used, such as max_length, current_num, and current_length, have constant space requirements and do not depend on the size of the input array.

Therefore, the overall space complexity of the code is O(n) due to the space used by the num_set.

Challenging Exercises:#

  1. Write an algorithm that not only returns the length of the longest consecutive elements sequence but also returns the actual consecutive sequence itself.

  2. Extend the problem to allow elements to be considered consecutive if they are within a certain absolute difference (e.g., less than or equal to k) instead of exactly 1. Write an algorithm that finds the longest such sequence and runs in O(n) time.