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

Function Signature:

from typing import List

def longest_consecutive(nums: List[int]) -> int:
    """
    Find the length of the longest consecutive elements sequence in an unsorted array.

    Parameters:
    - nums: A list of integers.

    Returns:
    - int: The length of the longest consecutive elements sequence.
    """
    # Your code here

Example:

result = longest_consecutive([100, 4, 200, 1, 3, 2])
print(result)  # Output: 4
# Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

result = longest_consecutive([0, 0, -1, 1, -2, 2, -3, 3])
print(result)  # Output: 7
# Explanation: The longest consecutive elements sequence is [-3, -2, -1, 0, 1, 2, 3]. Therefore its length is 7.

Note:

  • The input list may contain duplicates, but they should be ignored in the calculation of the longest consecutive sequence.
  • The input list may contain negative numbers.
  • If possible, please provide an algorithm with O(n) time complexity.

Instructions:

  • Write the longest_consecutive function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊