Problem of The Day: Longest Consecutive Sequence

Problem Statement

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.

 

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Intuition

The problem involves finding the length of the longest consecutive sequence in an unsorted array of integers. My initial thought is to use a set to efficiently check for the presence of numbers and explore consecutive sequences.

Approach

I plan to iterate through the numbers in the array and, for each unvisited number, extend a consecutive sequence by incrementing and decrementing until no more consecutive numbers are found. I will keep track of the visited numbers to avoid redundant processing. The length of each consecutive sequence will be compared to the current maximum length.

Complexity

• Time complexity: O(n), where n is the number of elements in the input array. The algorithm iterates through each element once.

• Space complexity: O(n), as the set “seen” stores the visited numbers.

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        set_nums = set(nums)
        seen = set()
        res = 0
        for num in nums:
            if num not in seen:
                lo, hi = num, num
                while num + 1 in set_nums:
                    hi = num + 1
                    num += 1
                    seen.add(hi)
                while num - 1 in set_nums:
                    lo = num - 1
                    num -= 1
                    seen.add(lo)
                res = max(res, hi - lo + 1)
                seen.add(num)
        return res
        

Union-Find Approach

# Helper class for making connected components 
class UnionFind:
    # Constructor
    def __init__(self, nums):
        self.parent = {num: num for num in nums}
        self.size = {num: 1 for num in nums}
        self.max_length = 1

    # Function to find the root of a sequence to which num1 belongs
    def find(self, num):
        if self.parent[num] != num:
            self.parent[num] = self.find(self.parent[num])
        return self.parent[num]

    # Function to merge the two sequences and updating lengths
    def union(self, num1, num2):
        x_root = self.find(num1)
        y_root = self.find(num2)
        if x_root != y_root:
            if self.size[x_root] < self.size[y_root]:
                x_root, y_root = y_root, x_root
            self.parent[y_root] = x_root
            self.size[x_root] += self.size[y_root]
            self.max_length = max(self.max_length, self.size[x_root])

from union_find import UnionFind

def longest_consecutive_sequence(nums):
    if not nums:
        return 0
    uf = UnionFind(nums)
    for num in nums:
        if num + 1 in nums:
            uf.union(num, num + 1)
    
    return uf.max_length

Explanation: The provided code implements the Union-Find data structure to find the length of the longest consecutive sequence in an array of numbers. The Union-Find class maintains parent and size information for each number. The find function identifies the root of a sequence, and the union function merges two sequences while updating their lengths. The longest_consecutive_sequence function creates a Union-Find instance and iterates through the numbers, performing unions for consecutive elements. The maximum length of any merged sequence is tracked and returned as the result.

Editorial Solution

class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0
        num_set = set(nums)

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

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

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

• Time Complexity: O(n)
• Space Complexity: O(n)