Solution 1: Brute Force

Intuition:

  • First, sort the array. This will make it easier to identify consecutive sequences.
  • Traverse the sorted array to find the longest consecutive sequence by counting the lengths of sequences of consecutive numbers.

Solution:

from typing import List

def longest_consecutive(nums: List[int]) -> int:
    if not nums:
        return 0
    
    # Step 1: Sort the array
    # ensures that consecutive numbers are next to each other
    nums.sort()
    
    longest_streak = 1
    current_streak = 1
    
    # Step 2: Traverse the sorted array
    for i in range(1, len(nums)):
    	
    	# Check if the current number is different from the previous one
        if nums[i] != nums[i - 1]:

        	# Check if it forms a consecutive sequence
            if nums[i] == nums[i - 1] + 1:
                current_streak += 1
            
            else:
            	# If we encounter a non-consecutive number, we compare the 
            	# current streak length with the longest streak found so far 
                longest_streak = max(longest_streak, current_streak)

                # Reset the current streak count.
				current_streak = 1
    
    # Final check for the last streak
    longest_streak = max(longest_streak, current_streak)
    
    return longest_streak

# Test cases
result = longest_consecutive([100, 4, 200, 1, 3, 2])
print(result)  # Output: 4

result = longest_consecutive([0, 0, -1, 1, -2, 2, -3, 3])
print(result)  # Output: 7

Time Complexity:

  • Sorting the array takes O(n log(n)) time.
  • Traversing the sorted array takes O(n) time.

Therefore, the overall time complexity of the brute force approach is O(n log(n)) due to the sorting step.

Space Complexity:

The space complexity is O(1) if we consider the sorting to be in-place. However, most sorting algorithms have O(n) space complexity due to the need for additional space for the sorting process.

Solution 2: Linear Time Complexity

Intuition:

To solve this problem in O(n) time complexity, we can use a set to efficiently check for the existence of elements:

  • Insert all elements into a set.
  • Iterate through the array, and for each element, check if it’s the start of a sequence (i.e., its predecessor is not in the set).
  • If it’s the start of a sequence, iterate to find the length of the sequence by checking the existence of consecutive elements.
  • Keep track of the maximum length found.

Solution:

from typing import List

def longest_consecutive(nums: List[int]) -> int:
    # Convert the list to a set for O(1) look-up times
    num_set = set(nums)
    longest_streak = 0

    # Iterate through each number in the set
    for num in num_set:
        # Check if it's the start of a sequence
        if num - 1 not in num_set:
            current_num = num
            current_streak = 1

            # Continue the sequence
            while current_num + 1 in num_set:
                current_num += 1
                current_streak += 1

            # Update the longest streak found
            longest_streak = max(longest_streak, current_streak)

    return longest_streak

# Test cases
result = longest_consecutive([100, 4, 200, 1, 3, 2])
print(result)  # Output: 4

result = longest_consecutive([0, 0, -1, 1, -2, 2, -3, 3])
print(result)  # Output: 7

Time Complexity:

The time complexity of this solution is O(n) because each element is processed a constant number of times (once when inserting into the set, and at most twice when checking for the start of a sequence and building the sequence).

Space Complexity:

The space complexity is O(n) due to the additional space used by the set to store the elements of the array.