Longest Consecutive Sequence

Find the length of the longest run of consecutive integers in an unsorted list.

hash set array linear consecutive

Write a function `longest_consecutive(nums)` that takes a list of integers `nums` and returns the length of the longest sequence of consecutive integers that appear in the list. The sequence elements can be in any order in the original list. Duplicates do not extend the sequence; each number is used at most once. Your solution must run in **O(n)** time and **O(n)** space, where n is the length of `nums`.

For example, `nums = [100, 4, 200, 1, 3, 2]` contains the consecutive sequence `1, 2, 3, 4`, so the answer is `4`. If `nums` is empty, return `0`.

**Function signature:** `def longest_consecutive(nums: list[int]) -> int:`

**Note:** Do not use sorting (that would be O(n log n)). Use a set to achieve O(n) time.

Constraints

0 ≤ len(nums) ≤ 10^5
-10^9 ≤ nums[i] ≤ 10^9
Time complexity: O(n)
Space complexity: O(n)

Example

>>> longest_consecutive([100, 4, 200, 1, 3, 2])
4
>>> longest_consecutive([1, 2, 0, 1])
3
>>> longest_consecutive([])
0
>>> longest_consecutive([9])
1

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a set to allow O(1) membership checks.

For each number, check if it is the start of a sequence (i.e., its predecessor is not in the set) and then count consecutive numbers upward.

Each number is visited at most twice, so the total is O(n).

Think about duplicates: they should not be counted again.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.