LeetCode 128: Longest Consecutive Sequence — Step-by-Step Visual Trace

Medium — Array | Hash Table | Union Find

The Problem

Given an unsorted array of integers, find the length of the longest sequence of consecutive elements. The algorithm must run in O(n) time complexity.

Approach

Convert the array to a set for O(1) lookups, then for each number that starts a sequence (has no predecessor), count consecutive numbers forward. This ensures each number is visited at most twice, maintaining O(n) time complexity.

Time: O(n) · Space: O(n)

Code

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_length = 0

        for num in num_set:
            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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments