DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Longest Consecutive Sequence

mediumArrays and hashing

Problem statement

You are given an unsorted list of integers nums. Return the length of the longest run of consecutive integer values that all appear in the list, such as 4, 5, 6, 7. Positions do not matter, only values. Duplicates count once.

Aim for O(n) time.

Examples

Example 1

Input: nums = [9, 1, 4, 7, 3, 2, 8]

Output: 4

Explanation: 1, 2, 3, 4 is the longest run. 7, 8, 9 has length 3.

Example 2

Input: nums = [5, 5, 6]

Output: 2

Explanation: The run is 5, 6. The repeated 5 does not make it longer.

Hints

Approach

Put all values in a set. A value x starts a run exactly when x - 1 is not in the set. From each start, count upward while the next value exists.

  1. Build present = set(nums).
  2. For each x in the set, skip it if x - 1 is present (it is in the middle of a run).
  3. Otherwise walk y = x, x + 1, ... while y + 1 is present.
  4. The run length is y - x + 1. Keep the maximum.

Why it is linear: every value is visited by the inner walk at most once, because only the start of its run begins a walk. Loop over the set rather than the list so repeated values do not start the same walk twice.

ComplexityTime O(n)Space O(n)
Python
class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
present = set(nums)
best = 0
for x in present:
if x - 1 in present:
continue # not the start of a run
y = x
while y + 1 in present:
y += 1
best = max(best, y - x + 1)
return best

Follow-up questions

  • Return the run itself (its first and last value), not just its length.
  • Values arrive one at a time. Maintain the longest run after each insert.

Frequently asked questions

The inner while only runs from the start of a run, and it walks that run once. Across the whole algorithm, each value is stepped over by an inner walk at most one time, so the total work is O(n).

Without it, you would start a walk from every value in a run. For a run of length n, that is n + (n - 1) + ... steps, which is quadratic again.

Finding contiguous ranges in a set of numbers is common: free port ranges, the longest stretch of consecutive healthy minutes, or runs of sequence numbers received without a gap. The same set-plus-start-check idea applies.