Leetcode - 128. Longest Consecutive Sequence

Medium

Dec 22, 2025

#hashmap

#math

128. Longest Consecutive Sequence

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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

0 <= nums.length <= 105
-109 <= nums[i] <= 109

Constraints:

Notes

Intuition

A number is the start of a consecutive sequence if there's no number exactly one less than it in the array. Once we identify a sequence start, we can count how long the sequence extends by checking for consecutive numbers.

Implementation

Store all numbers in a hashmap for O(1) lookup. Iterate through the array and check if each number is a sequence start (num - 1 not in map). If it is, walk forward counting consecutive numbers (num + 1, num + 2, etc.) and track the maximum length found.

Edge-cases

Duplicates can cause us to process the same sequence start multiple times. Initialize the hashmap with all False values and mark a sequence start as True once processed to avoid redundant work.

Time: O(n) — each number is part of at most one sequence traversal
Space: O(n) — hashmap stores all numbers

Complexity

Solution

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        map = {}
        for num in nums:
            map[num] = False

        max_sequence = 0
        for num in nums:
            is_sequence_start = num - 1 not in map
            if is_sequence_start and map[num] == False:
                map[num] = True # mark this sequence start as processed
                length = 0
                curr = num
                while curr in map:
                    curr += 1
                    length += 1
                max_sequence = max(max_sequence, length)


        return max_sequence
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()