Longest Consecutive Sequence

Problem

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

The solution must run in O(n) time.

Intuition

Sorting makes consecutive runs easy to detect, but sorting costs O(n log n), and the problem explicitly forbids that.

The trick is to stop asking "for every number, how long is the run containing it?" That repeats the same work.

Instead, only start counting from numbers that are actual sequence beginnings. A number x is a beginning if x - 1 is not present. Once you identify a beginning, walk upward until the run ends.

That "only start from beginnings" observation is what brings the complexity down to linear time.

Approach

use std::collections::HashSet;

impl Solution {
    pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
        let set: HashSet<i32> = nums.into_iter().collect();
        let mut best = 0;

        for &x in &set {
            if set.contains(&(x - 1)) {
                continue;
            }

            let mut y = x;
            while set.contains(&(y + 1)) {
                y += 1;
            }

            best = best.max(y - x + 1);
        }

        best
    }
}

function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;

  for (const x of set) {
    if (set.has(x - 1)) continue;

    let y = x;
    while (set.has(y + 1)) {
      y++;
    }

    best = Math.max(best, y - x + 1);
  }

  return best;
}

Edge cases

• Empty array — answer is 0.
• Duplicates — the set removes them automatically.
• Negative numbers — consecutive logic works the same on signed integers.

Takeaway

Linear-time set solutions often come from deleting repeated work, not from clever constant factors.

For this problem, the set is necessary but not sufficient. The real insight is to count only from sequence starts.