Log inSign up
mediumLeetCodeNot Started

Longest Consecutive Sequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

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.

Example 1 · Standard Unsorted Sequence:

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Its length is 4.

Example 2 · Sequence with Duplicates and Negative Numbers:

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9
Explanation: The longest consecutive elements sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Its length is 9.

Example 3 · Empty Array:

Input: nums = []
Output: 0
Explanation: Empty array has 0 consecutive elements.

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Hash Set insertion and lookup complexity
  • Understanding amortization in nested loops

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand amortized analysis of nested loops.
  • Master the 'Streak Starter' pruning check !set.has(x - 1) to achieve linear time.
  • Handle duplicate values and negative integers cleanly.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Contains DuplicateTwo Sum (Hash Table Lookups)Continuous Subarray Sum

1. Brute Force — Linear Search per Consecutive Element

Intuition

For every number, perform a full array linear scan for num+1, num+2, and so on until the consecutive chain terminates.

Algorithm

  1. Initialize required state variables and allocate data structures for Brute Force — Linear Search per Consecutive Element.
  2. Iterate through the input array and apply the core algorithmic condition.
  3. Update boundaries, frequencies, or pointers in accordance with the invariant.
  4. Return the computed result or transformed array.

Brute Force Linear Search for Consecutive Streaks

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [100, 4, 200, 1, 3, 2]
Current operationSTEP 1 OF 6
Candidate 100: Look for 101 in array
Visual state
Values and pointers at this exact step
array
S
100
4
200
1
3
2
0
↑ Start = 100
1
2
3
4
5
Variables at this step
Candidate
100
Current Streak
1
Max Streak
1
Check / comparison
Linear scan for 101: Not found. Streak = 1.
Decision / next transition
longestStreak = 1. Advance to next candidate.
Why this step matters

Candidate 100: Look for 101 in array. Not found. Streak length is 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8private:
9 bool arrayContains(const vector<int>& nums, int target) {
10 for (int x : nums) {
11 if (x == target) return true;
12 }
13 return false;
14 }
15
16public:
17 int longestConsecutive(vector<int>& nums) {
18 int longestStreak = 0;
19
20 for (int num : nums) {
21 int currentNum = num;
22 int currentStreak = 1;
23
24 while (arrayContains(nums, currentNum + 1)) {
25 currentNum += 1;
26 currentStreak += 1;
27 }
28
29 longestStreak = max(longestStreak, currentStreak);
30 }
31
32 return longestStreak;
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<int> nums = {100, 4, 200, 1, 3, 2};
39 cout << "Input: [100, 4, 200, 1, 3, 2]\n";
40 cout << "Brute Force Longest Consecutive: " << sol.longestConsecutive(nums) << "\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force — Linear Search per Consecutive Element.
  • Space complexity: O(1) — Space complexity for Brute Force — Linear Search per Consecutive Element.

Why Brute Force Doesn't Scale:

For N = 100,000, sorting takes ~1,700,000 operations.

Hash Set starter check processes N = 100,000 in ~100,000 lookups (linear runtime).

2. Better — Sorting and Counting

Intuition

Sort the array. Consecutive numbers will be adjacent. Traverse the sorted array, skipping duplicates and tracking running streak length.

Algorithm

  1. Sort the array
  2. Consecutive numbers will be adjacent
  3. Traverse the sorted array, skipping duplicates and tracking running streak length.

Sorting and Consecutive Element Counting Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 100, 200]
Current operationSTEP 1 OF 6
Phase 1 — Sort: Sorting arranges consecutive numbers contiguously
Visual state
Values and pointers at this exact step
array
S
1
2
3
4
100
200
0
↑ Sort Pass
1
2
3
4
5
Variables at this step
Sorted Array
[1, 2, 3, 4, 100, 200]
Check / comparison
Sort array: [100, 4, 200, 1, 3, 2] -> [1, 2, 3, 4, 100, 200].
Decision / next transition
Consecutive elements are now ordered linearly.
Why this step matters

Phase 1 — Sort: Sorting arranges consecutive numbers contiguously.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int longestConsecutive(vector<int>& nums) {
10 if (nums.empty()) return 0;
11
12 sort(nums.begin(), nums.end());
13 int longestStreak = 1;
14 int currentStreak = 1;
15
16 for (size_t i = 1; i < nums.size(); i++) {
17 if (nums[i] != nums[i - 1]) {
18 if (nums[i] == nums[i - 1] + 1) {
19 currentStreak++;
20 } else {
21 longestStreak = max(longestStreak, currentStreak);
22 currentStreak = 1;
23 }
24 }
25 }
26
27 return max(longestStreak, currentStreak);
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<int> nums = {100, 4, 200, 1, 3, 2};
34 cout << "Input: [100, 4, 200, 1, 3, 2]\n";
35 cout << "Better (Sorting) Longest Consecutive: " << sol.longestConsecutive(nums) << "\n";
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better — Sorting and Counting.
  • Space complexity: O(N) — Space complexity for Better — Sorting and Counting.

3. Optimal — Hash Set + Sequence Start Check

Intuition

Insert all numbers into an unordered set. Iterate through the set. If num - 1 does NOT exist in the set, num is the first element of a streak. From num, count upwards as long as num + 1, num + 2... are in the set.

Algorithm

  1. Insert all numbers into an unordered set
  2. Iterate through the set
  3. If num - 1 does NOT exist in the set, num is the first element of a streak
  4. From num, count upwards as long as num + 1, num + 2... are in the set.

Intelligent Sequence Head Search with Hash Set Trace

2 of 2 questions left today
Step 1 / 8
Trace timeline13% explored
InputINPUT nums = [100, 4, 200, 1, 3, 2]
Current operationSTEP 1 OF 8
Step 1 — Set Population: Add all elements to hash set in $O(N)$ time
Visual state
Values and pointers at this exact step
array
S
100
4
200
1
3
2
0
↑ Insert to Set
1
2
3
4
5
Variables at this step
numSet Size
6
Time
O(N)
Check / comparison
Insert all elements into hash set: numSet = { 100, 4, 200, 1, 3, 2 }.
Decision / next transition
Enables O(1) average time lookups.
Why this step matters

Step 1 — Set Population: Add all elements to hash set in O(N) time.

Step 1 / 8
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_set>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 int longestConsecutive(vector<int>& nums) {
11 unordered_set<int> numSet(nums.begin(), nums.end());
12 int longestStreak = 0;
13
14 for (int num : numSet) {
15 // Check if num is the start of a sequence
16 if (!numSet.count(num - 1)) {
17 int currentNum = num;
18 int currentStreak = 1;
19
20 while (numSet.count(currentNum + 1)) {
21 currentNum += 1;
22 currentStreak += 1;
23 }
24
25 longestStreak = max(longestStreak, currentStreak);
26 }
27 }
28
29 return longestStreak;
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> nums = {100, 4, 200, 1, 3, 2};
36 cout << "Input: [100, 4, 200, 1, 3, 2]\n";
37 cout << "Optimal Longest Consecutive: " << sol.longestConsecutive(nums) << "\n";
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal — Hash Set + Sequence Start Check.
  • Space complexity: O(1) — Space complexity for Optimal — Hash Set + Sequence Start Check.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan per ElementO(N^3)O(1)For each element x, linearly search for x + 1, x + 2... in the array until the sequence breaks.Repeated linear scans over the entire array for each number in the sequence.
2.Better — Sorting and CountingO(N log N)O(1)Sort the array in ascending order. Iterate through elements, increment streak if nums[i] == nums[i-1] + 1, skip if duplicate, reset to 1 otherwise.Comparison sorting time.
3.Optimal — Hash Set + Streak Starter CheckOptimalO(N)O(N)Insert all elements into a Hash Set. Only initiate a while loop when num - 1 is NOT in the set. Increment currNum and currentStreak while currNum + 1 exists in the set.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Longest Consecutive Sequence?

2.Why is the brute force approach suboptimal for large inputs in Longest Consecutive Sequence?

3.Which data structure or technique enables the optimal solution for Longest Consecutive Sequence?

Back to DSA Sheet