Longest Consecutive Sequence

LeetCode 128 · View on LeetCode

Put all numbers in a set. Only start counting from the beginning of a sequence (where num - 1 is not in the set). This ensures O(n) time.

def longest_consecutive(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0
    for num in num_set:
        if num - 1 not in num_set:
            length = 1
            while num + length in num_set:
                length += 1
            longest = max(longest, length)
    return longest

if __name__ == '__main__':
    print(longest_consecutive([100, 4, 200, 1, 3, 2]))    # 4
    print(longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6]))  # 9
    print(longest_consecutive([]))                          # 0