algoadvance

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.

Clarifying Questions

1. Can the array contain negative numbers?
   • Yes, the array can contain negative numbers.
2. Can the array be empty?
   • Yes, the array can be empty, and in that case, the longest consecutive sequence would be 0.
3. What is the range of the elements within the array?
   • The range of the elements is typical of integer values within Python’s capabilities.
4. Can elements be repeated in the array?
   • Yes, the array can contain duplicate elements, but duplicates should only count once in any sequence.

Strategy

The key to solving this problem efficiently (in O(n) time complexity) is to use a set for O(1) average time complexity for checking the existence of elements.

Here’s the step-by-step strategy:

1. Convert the List to a Set: Converting the list to a set helps in O(1) average time complexity for checking the presence of elements.

2. Iterate through the Set: For each element, check if it is the start of a sequence by verifying that the element minus one (num - 1) is not in the set.

3. Count the Length of the Sequence: If an element is the start of a sequence, count the length of the sequence by checking how many consecutive numbers follow it.

4. Track the Maximum Length: Keep track of the maximum length of all found sequences.

Code

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

    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Only start counting if num is the start of a sequence
        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

Time Complexity

• Conversion to Set: O(n), where n is the number of elements in nums.
• Iteration Through the Set: O(n), since in the worst case, each element is checked and each sequence is counted once.

Thus, the overall time complexity is O(n). The space complexity is also O(n) due to storing the elements in a set.

Summary

• Convert the list to a set for quick look-ups.
• Check each element to see if it could be the start of a sequence.
• Count the length of the sequence starting from such an element.
• Track and return the maximum sequence length found.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?