Longest Consecutive Sequence — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Hashing and solve the Longest Consecutive Sequence problem optimally.
O(N)O(N)Problem Description
Given an unsorted integer array nums, compute the size of the largest subset that can be reordered to form a sequence of consecutive integers. The subset may be any selection of elements; the original ordering is irrelevant. Return the length of this longest consecutive run.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Consecutive Sequence"
WHY DOES IT MATTER?
This pattern demonstrates the power of using auxiliary data structures to reduce time complexity by trading space for time. It is a fundamental technique for problems where order is irrelevant but membership queries are frequent. Mastering this pattern helps in solving a wide range of problems involving set operations, frequency counting, and sequence detection.
OPTIMIZATION CHALLENGE
The key challenge is avoiding redundant traversal of sequences. By only starting the count from the beginning of a sequence (where $x-1$ is not present), we ensure that each element is part of only one counting operation. This reduces the total number of inner loop iterations from $O(N^2)$ to $O(N)$.
REAL-WORLD CONNECTION
Consider a log analysis system where you need to find the longest streak of consecutive successful API calls. The timestamps are unsorted and arrive in a stream. Using a hash set to store timestamps allows you to quickly check if a timestamp is part of a consecutive run, enabling real-time detection of streaks without sorting the entire log, which would be too slow for high-throughput systems.
In interviews, explicitly state that you are using a HashSet to achieve $O(1)$ lookups. Emphasize the condition if (x - 1 not in set) to justify why the inner loop runs in $O(N)$ total time. This shows a deep understanding of amortized analysis and avoids the common pitfall of assuming the inner loop is $O(N)$ per element.
COMPLEXITY AT A GLANCE
O(N)O(N)Core Theory — Why This Approach?
The Longest Consecutive Sequence problem is a canonical example of using hashing to transform an $O(N \log N)$ sorting-based problem into an $O(N)$ linear-time solution. The naive approach involves sorting the array and scanning for consecutive runs, which is efficient but suboptimal for massive datasets where the logarithmic factor becomes significant. The optimal paradigm relies on the mathematical property that a consecutive sequence $[x, x+1, \dots, x+k]$ has a unique starting element $x$ such that $x-1$ does not exist in the set. By identifying only these starting points, we can traverse each sequence exactly once, ensuring that every element is visited a constant number of times on average.
Interview Questions on This Problem
Q1At a fintech platform processing millions of transaction IDs, how would you adapt the Longest Consecutive Sequence algorithm to handle duplicate IDs efficiently without increasing space complexity significantly?
Use a HashSet to store unique transaction IDs. Since the problem asks for the longest sequence of consecutive integers, duplicates do not extend the sequence length. By inserting all IDs into a set, we automatically deduplicate them in $O(N)$ time. The subsequent logic remains unchanged: iterate through the set, check for the start of a sequence, and count forward. This ensures that the space complexity remains $O(N)$ for unique elements, and the time complexity stays $O(N)$.
Q2In a distributed system where data is sharded across multiple nodes, how would you compute the global longest consecutive sequence if each node only has a subset of the data?
This requires a two-phase approach. First, each node computes the local longest consecutive sequences and identifies the start and end of each local run. These boundary pairs are sent to a coordinator. The coordinator merges these intervals by sorting them by start value and checking for overlaps or adjacency (where end of one + 1 == start of another). The longest merged interval gives the global answer. This reduces the problem to interval merging, which is $O(M \log M)$ where $M$ is the number of local runs, typically much smaller than $N$.
Q3How would you modify the algorithm to return the actual sequence of numbers, not just the length, while maintaining $O(N)$ time complexity?
When counting the length of a sequence starting at $x$, store the current maximum length and the starting number. Once the loop completes, you have the start and length of the longest sequence. To return the actual sequence, you can generate it by iterating from the start to start + length - 1. This post-processing step is $O(K)$ where $K$ is the length of the longest sequence, which is acceptable if $K$ is small relative to $N$. If $K$ is large, the output size itself dominates the complexity.
Examples
Input
[100,4,200,1,3,2]
Output
4
Explanation: The numbers 1,2,3,4 are all present, forming a consecutive block of length 4, which is longer than any other possible block.
Input
[0,-1,1,2,-2,5]
Output
5
Explanation: The values -2,-1,0,1,2 appear in the array, giving a consecutive sequence of length 5. No longer consecutive set exists.
Input
[10,5,12,3,55,4,11,2,6]
Output
5
Explanation: Elements 2,3,4,5,6 constitute a consecutive segment of length 5. Other segments such as 10,11,12 are shorter.
Constraints
- 1 <= nums.length <= 100000
- -10^9 <= nums[i] <= 10^9
- All entries are integers
- Expected time complexity O(n) with O(n) auxiliary space
Optimal Approach & Strategy
Use a HashSet to store all elements for O(1) lookups. For each element, check if it is the start of a sequence (i.e., x-1 is not in the set), and if so, count the length of the sequence by checking for x+1, x+2, etc., in the set.
Brute Force Approach
Sort the array in O(N log N) time and then iterate through it to find the longest run of consecutive integers. This approach is simple but suboptimal for large datasets due to the logarithmic factor in sorting.
Code Solutions
function longestConsecutive(nums){
const set = new Set(nums);
let best = 0;
for(const x of set){
if(!set.has(x-1)){
let cur = x;
let len = 0;
while(set.has(cur)){
len++; cur++;
}
if(len>best) best = len;
}
}
return best;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0){process.exit(0);}const n = input[0];const nums = input.slice(1,1+n);console.log(longestConsecutive(nums).toString());#include <bits/stdc++.h>
using namespace std;
int longestConsecutive(const vector<int>& nums){
unordered_set<int> s(nums.begin(), nums.end());
int best = 0;
for(int x: s){
if(s.find(x-1)==s.end()){
int cur = x;
int len = 0;
while(s.find(cur)!=s.end()){
++len; ++cur;
}
best = max(best, len);
}
}
return best;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n; if(!(cin>>n)) return 0;vector<int> a(n);for(int i=0;i<n;++i)cin>>a[i];cout<<longestConsecutive(a);return 0;}
import java.io.*;
import java.util.*;
public class Main {
public static int longestConsecutive(int[] nums){
Set<Integer> set = new HashSet<>();
for(int v: nums) set.add(v);
int best = 0;
for(int x: set){
if(!set.contains(x-1)){
int cur = x;
int len = 0;
while(set.contains(cur)){
len++; cur++;
}
if(len>best) best = len;
}
}
return best;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()) return;
StringTokenizer st = new StringTokenizer(line);
int n = Integer.parseInt(st.nextToken());
int[] nums = new int[n];
int idx=0;
while(idx<n){
if(!st.hasMoreTokens()){
line = br.readLine();
if(line==null) break;
st = new StringTokenizer(line);
continue;
}
nums[idx++] = Integer.parseInt(st.nextToken());
}
System.out.print(longestConsecutive(nums));
}
}
import sys
def longest_consecutive(nums):
s = set(nums)
best = 0
for x in s:
if x-1 not in s:
cur = x
length = 0
while cur in s:
length += 1
cur += 1
best = max(best, length)
return best
def main():
data = sys.stdin.read().strip().split()
if not data:
return
n = int(data[0])
nums = list(map(int, data[1:1+n]))
print(longest_consecutive(nums))
if __name__ == "__main__":
main()
function longestConsecutive(nums){
const set = new Set(nums);
let best = 0;
for(const x of set){
if(!set.has(x-1)){
let cur = x;
let len = 0;
while(set.has(cur)){
len++; cur++;
}
if(len>best) best = len;
}
}
return best;
}
const fs = require('fs');
const input = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(input.length===0){process.exit(0);}const n = input[0];const nums = input.slice(1,1+n);console.log(longestConsecutive(nums).toString());
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.