Python Program to Find Longest Consecutive Sequence

You can find the longest consecutive sequence in a list by converting it to a set and checking for starts of sequences with if num - 1 not in nums_set, then counting consecutive numbers using a while loop; here is the key code snippet: nums_set = set(nums); for num in nums_set: if num - 1 not in nums_set: length = 1; while num + length in nums_set: length += 1.

Examples

Input[100, 4, 200, 1, 3, 2]

Output4

Input[1, 9, 3, 10, 4, 20, 2]

Output4

Input[]

Output0

How to Think About It

To find the longest consecutive sequence, first think about how to quickly check if a number is part of a sequence. Using a set lets you check membership fast. Then, for each number, check if it is the start of a sequence by seeing if the previous number is missing. If it is, count how many numbers come after it consecutively. Keep track of the longest count found.

Algorithm

1

Convert the list to a set for fast lookup.

2

Initialize a variable to store the longest sequence length as 0.

3

For each number in the set, check if the previous number is not in the set.

4

If it is the start of a sequence, count consecutive numbers by checking if next numbers exist in the set.

5

Update the longest sequence length if the current count is greater.

6

Return the longest sequence length.

Code

python

def longest_consecutive(nums):
    nums_set = set(nums)
    longest = 0
    for num in nums_set:
        if num - 1 not in nums_set:
            length = 1
            while num + length in nums_set:
                length += 1
            longest = max(longest, length)
    return longest

print(longest_consecutive([100, 4, 200, 1, 3, 2]))

Output

4

Dry Run

Let's trace [100, 4, 200, 1, 3, 2] through the code

1

Convert list to set

nums_set = {1, 2, 3, 100, 4, 200}

2

Initialize longest

longest = 0

3

Check each number if start of sequence

For num=1, 0 not in set, start counting

4

Count consecutive numbers from 1

Check 2, 3, 4 in set, length=4

5

Update longest

longest = max(0,4) = 4

6

Check other numbers

For num=2, 1 in set, skip; For num=100, 99 not in set, length=1; longest=4

Number	Is start?	Sequence length	Longest so far
1	Yes	4	4
2	No	-	4
3	No	-	4
4	No	-	4
100	Yes	1	4
200	Yes	1	4

Why This Works

Step 1: Use a set for fast lookup

Converting the list to a set lets us check if a number exists in constant time with in.

Step 2: Find sequence starts

A number is the start of a sequence if the previous number is not in the set, so we only count sequences once.

Step 3: Count consecutive numbers

From each start, count how many numbers come after it consecutively by checking num + length in the set.

Step 4: Track longest sequence

Keep updating the longest sequence length found to return the maximum at the end.

Alternative Approaches

Sorting and scanning

python

def longest_consecutive_sort(nums):
    if not nums:
        return 0
    nums.sort()
    longest = 1
    current = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i-1]:
            continue
        elif nums[i] == nums[i-1] + 1:
            current += 1
        else:
            longest = max(longest, current)
            current = 1
    return max(longest, current)

print(longest_consecutive_sort([100, 4, 200, 1, 3, 2]))

This method sorts the list first, then scans for consecutive numbers. It uses O(n log n) time due to sorting but less extra space.

Using Union-Find data structure

python

class UnionFind:
    def __init__(self, nums):
        self.parent = {x: x for x in nums}
        self.size = {x: 1 for x in nums}
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.size[rootX] < self.size[rootY]:
                rootX, rootY = rootY, rootX
            self.parent[rootY] = rootX
            self.size[rootX] += self.size[rootY]


def longest_consecutive_union_find(nums):
    if not nums:
        return 0
    uf = UnionFind(nums)
    nums_set = set(nums)
    for num in nums:
        if num + 1 in nums_set:
            uf.union(num, num + 1)
    return max(uf.size.values())

print(longest_consecutive_union_find([100, 4, 200, 1, 3, 2]))

This advanced method uses union-find to group consecutive numbers. It is efficient but more complex to implement.

Complexity: O(n) time, O(n) space

Time Complexity

Converting the list to a set takes O(n). Each number is checked once to see if it starts a sequence, and counting consecutive numbers also sums to O(n) overall.

Space Complexity

The set stores all numbers, so it uses O(n) extra space. The algorithm does not use extra space beyond this.

Which Approach is Fastest?

The set-based approach is fastest with O(n) time. Sorting-based is slower at O(n log n). Union-Find is efficient but more complex.

Approach	Time	Space	Best For
Set-based scanning	O(n)	O(n)	Fastest for large unsorted lists
Sorting and scanning	O(n log n)	O(1) or O(n)	Simple to implement, less extra space
Union-Find	O(n)	O(n)	Complex cases, grouping sequences explicitly