Longest Consecutive Sequence

Given an unsorted array of integers nums, find the longest run of values that are consecutive integers, such as 5, 6, 7, 8, and return its length.

The values in a run can appear anywhere in the array and in any order; only which values are present matters. Repeated values count once. An empty array has answer 0.

Your algorithm should run in O(n) time, so sorting is not the intended solution.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Hashing & Counting · problem 9 of 169

Start simple

Sort the values and scan for the longest run of +1 steps, skipping duplicates: O(n log n) time. (Checking every value with repeated linear searches is O(n³).)

The key idea

Load all values into a hash set so that "is x present?" takes O(1) time. Duplicates disappear automatically.

Now, for each value x in the set, ask whether x - 1 is also present. If it is, x sits in the middle of some run and counting from it would only rediscover part of a longer run, so skip it. If it is not, x is the start of a run: count upward x + 1, x + 2, … while the values exist, and update the best length.

Why is this linear even though there is a loop inside a loop? Each run is counted only from its single starting value, so every value in the set is visited by an inner "count upward" loop at most once. Across the whole algorithm the inner loops therefore do O(n) steps, and the outer loop does O(n) set lookups.

Complexity

• Time: O(n)
• Space: O(n)

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        values = set(nums)
        best = 0
        for x in values:
            if x - 1 in values:
                continue  # x is not the start of a run
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
        return best

JavaScript

var longestConsecutive = function(nums) {
  const values = new Set(nums);
  let best = 0;
  for (const x of values) {
    if (values.has(x - 1)) continue; // x is not the start of a run
    let length = 1;
    while (values.has(x + length)) length++;
    best = Math.max(best, length);
  }
  return best;
};

What the interviewer is checking

The interviewer wants to see you beat sorting with a hash set and, crucially, justify the amortised O(n) bound by only expanding from the start of each run.

Mistakes to avoid

• Counting upward from every element, which degrades to O(n²) on one long run.
• Iterating over the original array instead of the set, so a heavily duplicated run start is expanded repeatedly.
• Forgetting the empty array, or counting duplicates as extra length.

Follow-ups to expect

• Return the run itself, not just its length. (Remember the best start value.)
• Values arrive one at a time; keep the answer updated. (Union-find or boundary map.)
• What if memory is tight? (Sort in place, O(1) extra.)

In real software

Finding the longest unbroken streak of active days for a user, or the longest contiguous block of free IDs or ports in an allocator, uses the same set-based run detection.

Practice next