Longest Consecutive Sequence

Description

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

A consecutive sequence is a set of numbers where each number is exactly one more than the previous number (for example, 1, 2, 3, 4). The elements of the sequence do not need to be adjacent in the original array — they just need to exist somewhere in the array.

You must design an algorithm that runs in O(n) time.

Examples

Example 1

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

Output: 4

Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Even though these elements are scattered across the array at different positions, they form a chain of four consecutive integers. No other consecutive sequence in the array is longer — 100 stands alone and 200 stands alone.

Example 2

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]

Output: 9

Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has length 9. Despite being scattered and containing a duplicate (0 appears twice), these nine distinct values form one unbroken chain of consecutive integers.

Example 3

Input: nums = [1, 0, 1, 2]

Output: 3

Explanation: The longest consecutive sequence is [0, 1, 2], which has length 3. The duplicate value 1 does not extend the sequence — each value counts only once.

Constraints

0 ≤ nums.length ≤ 10^5
-10^9 ≤ nums[i] ≤ 10^9

Editorial

Brute Force

Intuition

The simplest way to think about this problem is: for every number in the array, try to build the longest consecutive chain starting from that number.

Imagine you pick up a number — say 3. You then ask: "Is 4 in the array? Yes. Is 5 in the array? Yes. Is 6 in the array? No." So the chain starting from 3 has length 3 (which is 3, 4, 5). You repeat this process for every number in the array and keep track of the longest chain you find.

The problem with this approach is that checking "is this number in the array?" by scanning the entire array takes O(n) time, and we might do that many times for each starting number, leading to very slow performance.

Step-by-Step Explanation

Let's trace through with nums = [100, 4, 200, 1, 3, 2]:

Step 1: Start with nums[0] = 100. Search for 101 in the array — not found. Chain length = 1.

Step 2: Move to nums[1] = 4. Search for 5 in the array — not found. Chain length = 1. Current longest = 1.

Step 3: Move to nums[2] = 200. Search for 201 — not found. Chain length = 1.

Step 4: Move to nums[3] = 1. Search for 2 — found! Search for 3 — found! Search for 4 — found! Search for 5 — not found. Chain length = 4 (1, 2, 3, 4). Update longest = 4.

Step 5: Move to nums[4] = 3. Search for 4 — found! Search for 5 — not found. Chain length = 2. Longest remains 4.

Step 6: Move to nums[5] = 2. Search for 3 — found! Search for 4 — found! Search for 5 — not found. Chain length = 3. Longest remains 4.

Result: The longest consecutive sequence has length 4.

Brute Force — Trying Every Starting Point — For each element, we linearly search the array for the next consecutive number, counting how long the chain grows before breaking.

Algorithm

Initialize longest = 0
For each element num in the array:
a. Set current_num = num, current_streak = 1
b. While current_num + 1 exists in the array (linear search):
- Increment current_num and current_streak
  c. Update longest = max(longest, current_streak)
Return longest

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int longest = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            int currentNum = nums[i];
            int currentStreak = 1;
            
            // Search for next consecutive numbers
            while (true) {
                bool found = false;
                for (int j = 0; j < nums.size(); j++) {
                    if (nums[j] == currentNum + 1) {
                        found = true;
                        break;
                    }
                }
                if (!found) break;
                currentNum++;
                currentStreak++;
            }
            
            longest = max(longest, currentStreak);
        }
        
        return longest;
    }
};

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        longest = 0
        
        for num in nums:
            current_num = num
            current_streak = 1
            
            # Search for next consecutive numbers
            while current_num + 1 in nums:
                # Note: 'in' on a list is O(n)
                current_num += 1
                current_streak += 1
            
            longest = max(longest, current_streak)
        
        return longest

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        
        int longest = 0;
        
        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i];
            int currentStreak = 1;
            
            while (arrayContains(nums, currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }
            
            longest = Math.max(longest, currentStreak);
        }
        
        return longest;
    }
    
    private boolean arrayContains(int[] nums, int target) {
        for (int num : nums) {
            if (num == target) return true;
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n³)

For each of the n elements, we try to extend a chain. Each extension step requires a linear search through the array (O(n)), and a chain can be up to n elements long. In the worst case (e.g., [1, 2, 3, ..., n]), starting from element 1 does n searches of O(n) each, giving O(n²) for that element alone. Across all n starting points, the total work is O(n³).

Space Complexity: O(1)

We only use a few integer variables to track the current chain and the longest seen. No extra data structures are allocated.

Why This Approach Is Not Efficient

The brute force has O(n³) time complexity. With n up to 10^5, this means up to 10^15 operations — far too slow to pass within any reasonable time limit.

There are two sources of waste:

Redundant chain-building: If the array is [1, 2, 3, 4], we build the chain 1→2→3→4 starting from 1, then again build 2→3→4 from 2, then 3→4 from 3. These are all subsets of the same sequence — massive duplication.
Linear search for existence: Each time we check "is the next number present?", we scan the entire array. A hash set would answer that question in O(1) instead of O(n).

The first insight — sorting the array — eliminates both problems partially. Consecutive elements become adjacent, so we just scan left to right.

Better Approach - Sorting

Intuition

If the array were sorted, consecutive elements would sit right next to each other. We would just need to scan from left to right and count how long each run of consecutive values is.

Think of it like organizing a scattered deck of numbered cards. Once you sort them in order, you can instantly see which cards form unbroken runs by just reading left to right: 1, 2, 3 — that's a run of 3. Then a gap. Then 7, 8 — a run of 2. You pick the longest run.

The only wrinkle is handling duplicates — if the same number appears twice, we skip the duplicate and continue the current run.

Step-by-Step Explanation

Let's trace through with nums = [100, 4, 200, 1, 3, 2]:

Step 1: Sort the array → [1, 2, 3, 4, 100, 200].

Step 2: Initialize current_streak = 1, longest = 1. Start scanning from index 1.

Step 3: Compare sorted[1]=2 with sorted[0]=1. Since 2 = 1 + 1, they are consecutive. Increment current_streak = 2.

Step 4: Compare sorted[2]=3 with sorted[1]=2. Since 3 = 2 + 1, consecutive. current_streak = 3.

Step 5: Compare sorted[3]=4 with sorted[2]=3. Since 4 = 3 + 1, consecutive. current_streak = 4.

Step 6: Compare sorted[4]=100 with sorted[3]=4. Since 100 ≠ 5, the run breaks. Update longest = max(1, 4) = 4. Reset current_streak = 1.

Step 7: Compare sorted[5]=200 with sorted[4]=100. Since 200 ≠ 101, the run breaks. longest remains 4. Reset current_streak = 1.

Result: longest = 4.

Sorting Approach — Scanning for Consecutive Runs — After sorting the array, we scan left to right counting consecutive runs and tracking the longest one found.

Algorithm

If the array is empty, return 0
Sort the array in ascending order
Initialize current_streak = 1, longest = 1
For each index i from 1 to n-1:
a. If nums[i] == nums[i-1] → skip (duplicate)
b. If nums[i] == nums[i-1] + 1 → increment current_streak
c. Else → update longest = max(longest, current_streak), reset current_streak = 1
Return max(longest, current_streak)

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        sort(nums.begin(), nums.end());
        
        int longest = 1;
        int currentStreak = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            // Skip duplicates
            if (nums[i] == nums[i - 1]) continue;
            
            if (nums[i] == nums[i - 1] + 1) {
                currentStreak++;
            } else {
                longest = max(longest, currentStreak);
                currentStreak = 1;
            }
        }
        
        return max(longest, currentStreak);
    }
};

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

import java.util.Arrays;

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

Complexity Analysis

Time Complexity: O(n log n)

The sorting step dominates at O(n log n). The subsequent scan is a single pass through the array in O(n) time. Combined: O(n log n + n) = O(n log n).

Space Complexity: O(1) or O(n)

If we sort in-place, the additional space is O(1) (ignoring the sort's internal stack for languages like Python that use Timsort with O(n) auxiliary space). In Java and C++, typical in-place sorts use O(log n) stack space.

Why This Approach Is Not Efficient

The sorting approach runs in O(n log n), which is a massive improvement over O(n³). However, the problem explicitly asks for an O(n) solution.

The bottleneck is the sort itself — comparison-based sorting cannot do better than O(n log n). We need to rethink the problem.

The key observation: we don't actually need the elements in order. We just need to quickly answer two questions for any number:

"Is this number in the array?" (existence check)
"Is this number the start of a consecutive chain?" (i.e., is num-1 absent?)

A hash set answers question 1 in O(1) time. And question 2 is just a single O(1) lookup. This means we can find all consecutive sequences in O(n) total time without sorting.

Optimal Approach - Hash Set

Intuition

The clever insight is this: not every number should be a starting point for chain-building. If a number num has num - 1 in the array, then num is part of a chain that started earlier — starting from num would be redundant work.

So we only start building a chain from numbers that have no predecessor — numbers where num - 1 does NOT exist in the set. These are the true "sequence starts."

For example, in [100, 4, 200, 1, 3, 2]:

1 has no predecessor (0 is not in the array) → 1 is a sequence start
2 has predecessor 1 → skip (it will be counted as part of 1's chain)
3 has predecessor 2 → skip
4 has predecessor 3 → skip
100 has no predecessor 99 → 100 is a sequence start
200 has no predecessor 199 → 200 is a sequence start

We only build chains from the three sequence starts (1, 100, 200), which means each element is visited exactly once across all chains. This gives us O(n) total time.

Step-by-Step Explanation

Let's trace through with nums = [100, 4, 200, 1, 3, 2]:

Step 1: Insert all elements into a hash set: {100, 4, 200, 1, 3, 2}.

Step 2: Check num = 100. Is 99 in the set? No → 100 is a sequence start. Count: 100 (is 101 in set? No). Chain length = 1.

Step 3: Check num = 4. Is 3 in the set? Yes → 4 is NOT a sequence start. Skip it.

Step 4: Check num = 200. Is 199 in the set? No → 200 is a sequence start. Count: 200 (is 201 in set? No). Chain length = 1.

Step 5: Check num = 1. Is 0 in the set? No → 1 is a sequence start. Count forward: 1 → 2 (in set) → 3 (in set) → 4 (in set) → 5 (not in set). Chain length = 4. Update longest = 4.

Step 6: Check num = 3. Is 2 in the set? Yes → NOT a sequence start. Skip.

Step 7: Check num = 2. Is 1 in the set? Yes → NOT a sequence start. Skip.

Result: longest = 4.

Hash Set — Finding Sequence Starts and Building Chains — Watch how we insert all elements into a hash set, then only build chains from elements with no predecessor, ensuring O(n) total work.

Algorithm

If the array is empty, return 0
Insert all elements into a hash set
Initialize longest = 0
For each element num in the array:
a. Check if num - 1 is in the set
b. If num - 1 is NOT in the set → num is a sequence start:
- Set current_num = num, current_streak = 1
- While current_num + 1 is in the set:
  - Increment current_num and current_streak
- Update longest = max(longest, current_streak)
  c. If num - 1 IS in the set → skip (not a start)
Return longest

Code

#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longest = 0;
        
        for (int num : numSet) {
            // Only start counting from sequence beginnings
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }
                
                longest = max(longest, currentStreak);
            }
        }
        
        return longest;
    }
};

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0
        
        num_set = set(nums)
        longest = 0
        
        for num in num_set:
            # Only start counting from sequence beginnings
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                
                longest = max(longest, current_streak)
        
        return longest

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int longest = 0;
        
        for (int num : numSet) {
            // Only start counting from sequence beginnings
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                longest = Math.max(longest, currentStreak);
            }
        }
        
        return longest;
    }
}

Complexity Analysis

Time Complexity: O(n)

Inserting n elements into the hash set takes O(n). The key insight for the iteration: although there is a while loop inside the for loop, each element is visited at most twice across the entire execution — once when checking if it is a sequence start, and once when it is reached during chain-building from its actual start. The total number of set lookups across all iterations is proportional to n, not n².

For example, with [1, 2, 3, 4, 100, 200]: element 1 triggers the while loop visiting 1→2→3→4 (4 lookups), but elements 2, 3, 4 are skipped by the start-check (3 lookups). Elements 100 and 200 each do 1 start-check + 1 chain lookup = 2 lookups each. Total ≈ 4 + 3 + 4 = 11 lookups for 6 elements — linear in n.

Space Complexity: O(n)

The hash set stores up to n unique elements. No other data structure grows with input size.

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

HARD

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

Longest Consecutive Sequence

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Sorting

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Hash Set

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis