Approach Summary
Put all numbers in a set. For each number that has no predecessor (n-1 not in set), count consecutive streak forward.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sorting Baseline | O(N log N) | O(1) or O(N) | Sorts the array and scans for adjacent elements differing by 1, skipping duplicates. |
| 2 Approach 2: Hash Set Intelligent Streak Counting (Optimal) | O(N) | O(N) | Inserts all elements into a hash set; only attempts counting streaks starting from elements x where x - 1 is absent. |
Step 1: Baseline
Approach 1: Sorting Baseline
Time: O(N log N)
Space: O(1) or O(N)
1. If array is empty, return 0. 2. Sort array in ascending order. 3. Maintain `longest` and `currentStreak = 1`. 4. Scan array from index 1 to N-1: - If `nums[i] == nums[i - 1]`, continue (duplicate). - If `nums[i] == nums[i - 1] + 1`, increment `currentStreak++`. - Else, update `longest = max(longest, currentStreak)` and reset `currentStreak = 1`. 5. Return `max(longest, currentStreak)`.
Approach 1: Sorting Baseline Implementation
Approach 1: Sorting Baseline
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Arrays.sort(nums);
int longest = 1, curr = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) continue;
if (nums[i] == nums[i - 1] + 1) curr++;
else {
longest = Math.max(longest, curr);
curr = 1;
}
}
return Math.max(longest, curr);
}
}class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if (nums.empty()) return 0;
sort(nums.begin(), nums.end());
int longest = 1, curr = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] == nums[i - 1]) continue;
if (nums[i] == nums[i - 1] + 1) curr++;
else {
longest = max(longest, curr);
curr = 1;
}
}
return max(longest, curr);
}
};class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
if not nums: return 0
nums.sort()
longest, curr = 1, 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]: continue
if nums[i] == nums[i - 1] + 1:
curr += 1
else:
longest = max(longest, curr)
curr = 1
return max(longest, curr)var longestConsecutive = function(nums) {
if (!nums.length) return 0;
nums.sort((a, b) => a - b);
let longest = 1, curr = 1;
for (let i = 1; i < nums.length; i++) {
if (nums[i] === nums[i - 1]) continue;
if (nums[i] === nums[i - 1] + 1) curr++;
else {
longest = Math.max(longest, curr);
curr = 1;
}
}
return Math.max(longest, curr);
}; Step 2: Most Optimized
Approach 2: Hash Set Intelligent Streak Counting (Optimal)
Time: O(N)
Space: O(N)
1. Insert all array values into a Hash Set in O(N) time. 2. Iterate through each number `x` in the set. 3. Check if `x - 1` is in the set. If it is, skip `x` because it cannot be the head of a streak. 4. If `x - 1` is absent, initialize `streak = 1` and loop while `set.contains(x + 1)`, incrementing `x` and `streak`. 5. Record `max(result, streak)`. 6. Guaranteed O(N) total runtime because each streak component is traversed only once.
Approach 2: Hash Set Intelligent Streak Counting (Optimal) Implementation
Approach 2: Hash Set Intelligent Streak Counting (Optimal)
class Solution {
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);
int longest = 0;
for (int x : set) {
if (!set.contains(x - 1)) {
int curr = x, streak = 1;
while (set.contains(curr + 1)) {
curr++;
streak++;
}
longest = Math.max(longest, streak);
}
}
return longest;
}
}class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int longest = 0;
for (int x : s) {
if (s.find(x - 1) == s.end()) {
int curr = x, streak = 1;
while (s.find(curr + 1) != s.end()) {
curr++;
streak++;
}
longest = max(longest, streak);
}
}
return longest;
}
};class Solution:
def longestConsecutive(self, nums: list[int]) -> int:
num_set = set(nums)
longest = 0
for x in num_set:
if x - 1 not in num_set:
curr, streak = x, 1
while curr + 1 in num_set:
curr += 1
streak += 1
longest = max(longest, streak)
return longestvar longestConsecutive = function(nums) {
const set = new Set(nums);
let longest = 0;
for (const x of set) {
if (!set.has(x - 1)) {
let curr = x, streak = 1;
while (set.has(curr + 1)) {
curr++;
streak++;
}
longest = Math.max(longest, streak);
}
}
return longest;
};Edge Cases to Watch
- Empty array — return 0
- Single element array — return 1
- Duplicates present (e.g. [1, 2, 0, 1]) — hash set naturally deduplicates them without affecting sequence length
- Negative numbers and large gaps (e.g. [-5, -4, 100, 200]) — streak starts correctly at -5 with length 2
Algorithmic Pattern
View Pattern Guide →
Master the Hash Map / Set Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Hash Map / Set pattern.
Framework: Hash Map / Set • Interview Prep: Tested at FAANG •
Explore all Hash Map / Set problems & invariants →
How to Recognize This Pattern
- Longest consecutive streak
- O(n) required
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Hash Set
Frequently Asked Questions
What is the optimal time and space complexity for Longest Consecutive Sequence?
The optimal solution for Longest Consecutive Sequence achieves O(n) runtime complexity and requires O(n) auxiliary space. Time Complexity is O(N) where N is the length of the array. Inserting elements into the hash set takes O(N) average time. In the sequence check, inner while loops only execute for numbers that are the first element of a streak. Across the entire array, each element is part of exactly one streak, so inner lookups sum to N total steps. Space Complexity is O(N) to store the distinct elements in the hash set.
How do I identify that Longest Consecutive Sequence requires the Hash Map / Set pattern?
In technical interviews, look for key problem signals: Longest consecutive streak; O(n) required. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Hash Map / Set strategy.
What critical edge cases must be handled in Longest Consecutive Sequence?
Essential edge cases to verify include: Empty array — return 0; Single element array — return 1; Duplicates present (e.g. [1, 2, 0, 1]) — hash set naturally deduplicates them without affecting sequence length; Negative numbers and large gaps (e.g. [-5, -4, 100, 200]) — streak starts correctly at -5 with length 2. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Longest Consecutive Sequence?
Longest Consecutive Sequence is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Google, Facebook, Amazon.