Longest Consecutive Sequence (LC 128)

Pattern: HashSet + “graph” of consecutive integers
Difficulty: Medium
Key Concept: Treat each number as a node with edges to n-1 and n+1; avoid O(n²) by only starting a streak at n when n-1 is missing.

Problem Statement

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

You must run in O(n) time.

Input: int[] nums
Output: int

Example: [100,4,200,1,3,2] → sequence 1,2,3,4 → length 4.

---

1. Algorithm & Pseudocode

Brute force

1. Sort the array, scan for longest run of consecutive values — O(n log n).
2. Or: for each nums[i], linearly count nums[i]+1, nums[i]+2, ... with repeated linear lookups — O(n²) with array scans; O(n) per start with HashSet lookups but still O(n²) if every element starts a streak.

Optimal

put all nums in a HashSet S
longest = 0
for each x in S:
  if (x - 1) not in S:        // x is start of a streak
    y = x
    len = 0
    while y in S:
      len++
      y++
    longest = max(longest, len)
return longest

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Set membership in O(1) lets you walk x, x+1, x+2, ... quickly.
• Start only at sequence beginnings: If x-1 exists, x is not the left end; you’ll count the same streak when you start from x-1. That guarantees each integer is visited in an inner while at most once across the whole algorithm → O(n) total.

---

3. The Dry Run

nums = [100, 4, 200, 1, 3, 2] → S = {100,4,200,1,3,2}

x	x-1 in S?	Action	streak len	best
100	99 no	walk 100,101 stops	1	1
4	3 yes	skip start	—	1
200	199 no	walk 200 only	1	1
1	0 no	walk 1,2,3,4	4	4
3	2 yes	skip	—	4
2	1 yes	skip	—	4

Answer 4.

---

4. Java Solution

Brute Force

Sort and scan

import java.util.*;

class SolutionBrute {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        Arrays.sort(nums);
        int best = 1, cur = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) continue;
            if (nums[i] == nums[i - 1] + 1) cur++;
            else cur = 1;
            best = Math.max(best, cur);
        }
        return best;
    }
}

Time: O(n log n), Space: O(1) if sort in place (excluding sort aux).

Naive double loop (try every element as start):

import java.util.*;

class SolutionNaive {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) s.add(x);
        int best = 0;
        for (int x : s) {
            int len = 0, y = x;
            while (s.contains(y)) {
                len++;
                y++;
            }
            best = Math.max(best, len);
        }
        return best;
    }
}

Time: O(n²) worst case (e.g., dense interval — every x starts a long inner walk).

Optimal

import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) s.add(x);

        int best = 0;
        for (int x : s) {
            if (s.contains(x - 1)) continue;
            int len = 1;
            while (s.contains(x + len)) len++;
            best = Math.max(best, len);
        }
        return best;
    }
}

Time: O(n) — each number entered in at most one forward walk.
Space: O(n) for the set.

---

5. The “Java vs. Others” Edge

• HashSet<Integer> for boxed ints is standard; for primitive-heavy workloads, third-party IntOpenHashSet (Eclipse Collections / fastutil) avoids boxing — rarely needed in interviews.
• Duplicates in nums: adding to a set dedupes automatically.
• long for x + len if you worry overflow on extreme values — LeetCode ints are fine with while (s.contains(x + len)) if you increment carefully (alternative: y = x; while (s.contains(y+1)) y++;).

---

6. Complexity Summary

Approach	Time	Space	Notes
Sort + scan	O(n log n)	O(1)	Violates O(n) requirement
Set + naive starts	O(n²) worst	O(n)	Missing x-1 guard
Set + start at heads	O(n)	O(n)	Optimal

---

ASCII: Streaks as 1D “graph”

nums on number line:

  ...  1 — 2 — 3 — 4     100     200 ...
       ^start only here
       (4 doesn't start: 3 exists)

Edges implied: n — (n+1) if both in set