Longest Consecutive Sequence

medium array hash set

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Drop everything into a set. Only start counting a run from a value that has no predecessor in the set — otherwise we'd double-count. From a true run start, walk +1, +1, +1 until the chain breaks.

Inputnums = [102, 4, 200, 1, 3, 2, 101, 100]

Output4

The run 1, 2, 3, 4 has length 4 (longer than 100, 101, 102 of length 3).

nums (comma-separated)

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for v in s:
        if v - 1 in s:
            continue
        cur, length = v, 1
        while cur + 1 in s:
            cur += 1
            length += 1
        if length > best:
            best = length
    return best

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const v of set) {
    if (set.has(v - 1)) continue;
    let cur = v, length = 1;
    while (set.has(cur + 1)) { cur++; length++; }
    if (length > best) best = length;
  }
  return best;
}

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) set.add(x);
        int best = 0;
        for (int v : set) {
            if (set.contains(v - 1)) continue;
            int cur = v, length = 1;
            while (set.contains(cur + 1)) { cur++; length++; }
            if (length > best) best = length;
        }
        return best;
    }
}

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int best = 0;
    for (int v : s) {
        if (s.count(v - 1)) continue;
        int cur = v, length = 1;
        while (s.count(cur + 1)) { cur++; length++; }
        if (length > best) best = length;
    }
    return best;
}

Explanation

Sorting would solve this easily but costs O(n log n). The clever trick uses a hash set to find the longest run of consecutive numbers in plain linear time.

First, drop every number into a set s so we can ask "is value X present?" instantly. The key insight: only count a run starting from a value that has no predecessor in the set. If v - 1 is also present, then v is in the middle of some run and we'd be double-counting — so we skip it.

When v - 1 is missing, v is a true run start. From there we keep checking v+1, v+2, and so on, growing length until the chain breaks. We track the best length seen.

Example: nums = [102, 4, 200, 1, 3, 2, 101, 100]. Value 1 has no 0 before it, so it starts a run: 1, 2, 3, 4 — length 4. Value 100 starts another run 100, 101, 102 — length 3. The answer is 4.

Even though there's a loop inside a loop, each number is visited at most twice overall (once as a skip-check, once while extending exactly one run), so the total work stays linear on average.

Time: O(n) avg. Space: O(n)