LeetCode · #128

Longest Consecutive Sequence Solution

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #128

🏗️

Pattern

Hash Set — sequence head detection

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. For example, [1, 2, 3, 4] is a consecutive sequence of length 4. You must write an algorithm that runs in O(n) time.

Example

 Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4 // The longest consecutive sequence is [1, 2, 3, 4] — length 4 

Constraints

 • 0 ≤ nums.length ≤ 10⁵ • -10⁹ ≤ nums[i] ≤ 10⁹  ↑ Must be O(n) — sorting is O(n log n) so we need a different approach 

Section Two · Approach 1

Brute Force — Sort O(n log n)

Sort the array, then scan for consecutive runs. Track the current streak length and update the maximum whenever the streak breaks.

Why it works

After sorting, consecutive numbers are adjacent. A linear scan finds all consecutive runs by checking if nums[i] == nums[i-1] + 1.

Why we can do better

Problem: Sorting costs O(n log n) — the problem requires O(n). A HashSet lets us check "does num+1 exist?" in O(1), and the key insight is to only start counting from sequence heads — numbers where num-1 is NOT in the set.

Java — Sort + Scan

 import java.util.Arrays;
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Arrays.sort(nums);
int longest = 1, streak = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) continue; // skip duplicates if (nums[i] == nums[i - 1] + 1) streak++;
else streak = 1;
            longest = Math.max(longest, streak);
        }
return longest;
    }
}

Python — Sort + Scan

 class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
if not nums:
return 0
nums.sort()
        longest = streak = 1 for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
continue if nums[i] == nums[i - 1] + 1:
                streak += 1 else:
                streak = 1
longest = max(longest, streak)
return longest

Metric	Value
Time	O(n log n) — dominated by sort
Space	O(1) — or O(n) depending on sort implementation

Section Three · Approach 2

HashSet — O(n)

Put all numbers in a HashSet. For each number, check if it's the start of a sequence (i.e., num-1 is NOT in the set). If it is, count consecutive numbers forward: num, num+1, num+2, ... Track the maximum length.

💡 Mental model: Imagine numbered dominoes scattered on a table. To find the longest chain, don't start from every domino — that wastes time. Instead, only pick up a domino if it's the leftmost piece of a potential chain (no piece to its left). From there, snap consecutive pieces together rightward. The longest chain you build is your answer.

Algorithm — Sequence-head detection

Step 1: Add all elements to a HashSet (deduplicates automatically).
Step 2: For each number in the set, check if num - 1 exists. If it does, skip — this number is NOT a sequence head.
Step 3: If num - 1 is absent, this IS a head. Count forward: num, num+1, num+2, ... while each successor exists in the set.
Step 4: Update the maximum length. Return it after processing all elements.

🎯 When to recognize this pattern:

Any problem that asks for consecutive ranges in an unsorted collection — think HashSet + sequence-head detection.
The signal is "find longest run" or "count sequences" without sorting.
The trick is to only start counting from heads to avoid redundant work.
This pattern is specific to LC 128 but the "head detection" idea generalizes to union-find problems.

Why it's O(n) despite nested loops:

The inner while-loop only runs for sequence heads, and each element is visited at most twice — once in the outer loop and once as part of a forward count.
Total work across all iterations is O(n), not O(n²).

Section Four · Trace

Visual Walkthrough

Trace through nums = [100, 4, 200, 1, 3, 2]:

HashSet — sequence-head detection

Notice:

Elements 4, 3, 2 were skipped because they have predecessors in the set.
Only sequence heads (1, 100, 200) trigger the counting loop. This prevents redundant work and keeps total time at O(n).

Section Five · Implementation

Code — Java & Python

Java — HashSet sequence-head

 import java.util.HashSet;
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);
int longest = 0;
for (int num : set) {
if (set.contains(num - 1)) continue; // not a head — skip int length = 1;
while (set.contains(num + length)) // count forward
length++;

            longest = Math.max(longest, length);
        }
return longest;
    }
}

Python — set sequence-head

 class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
        num_set = set(nums)
        longest = 0 for num in num_set:
if num - 1 in num_set:
continue # not a head — skip
length = 1 while num + length in num_set:
                length += 1
longest = max(longest, length)
return longest

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Sort + Scan	O(n log n)	O(1)	Violates O(n) requirement; modifies input
Brute Force (check each)	O(n³)	O(1)	For each element, search array for next consecutive
HashSet ← optimal	O(n)	O(n)	O(1) lookups; each element visited at most twice

Why not Union-Find?:

Union-Find also achieves O(n·α(n)) ≈ O(n) — but it's more complex to implement for this specific problem.
HashSet with head detection is cleaner, more intuitive, and strictly O(n) without the inverse-Ackermann constant.
Use Union-Find when you need to merge dynamic ranges, not for static one-pass problems.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty array	`[]`	Return 0 — no elements, no sequence.
Single element	`[7]`	One element is a sequence of length 1.
Duplicates	`[1,2,2,3]`	HashSet deduplicates automatically. Sequence is [1,2,3] → length 3.
Negative numbers	`[-3,-2,-1,0]`	Negatives form valid sequences. Head is -3 (no -4 in set).
All same value	`[5,5,5]`	Set becomes {5}. 5 is a head (4 absent). Length 1.
Disjoint sequences	`[1,3,5,7]`	Four sequences of length 1. Each is its own head.

⚠ Common Mistake: Iterating over the original array instead of the set. If you iterate over nums and it has duplicates, you'll process the same head multiple times — degrading performance. Always iterate over the set view to avoid redundant work.

← Back to Arrays & Hashing problems

LearningTree

LC 128 · Longest Consecutive Sequence — Solution & Explanation | DSA Guide