Longest Consecutive Sequence [Medium] — HashSet O(n)
Sanjeev SharmaAdvertisement
Problem Statement
Find the length of the longest consecutive integer sequence.
Input: [100,4,200,1,3,2] → Output: 4 ([1,2,3,4])
Input: [0,3,7,2,5,8,4,6,0,1] → Output: 9
Intuition
Put all in a HashSet. For each n, only start counting if n-1 is not in the set (n is the start of a sequence). Count up while n+1 is in set.
Solutions
C++
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(),nums.end());
int best=0;
for(int n:s) if(!s.count(n-1)){
int cur=n,len=1;
while(s.count(++cur)) len++;
best=max(best,len);
}
return best;
}
Java
public int longestConsecutive(int[] nums) {
Set<Integer> s=new HashSet<>(); for(int n:nums) s.add(n);
int best=0;
for(int n:s) if(!s.contains(n-1)){
int cur=n,len=1;
while(s.contains(++cur)) len++;
best=Math.max(best,len);
}
return best;
}
Python
def longestConsecutive(nums: list[int]) -> int:
s = set(nums)
best = 0
for n in s:
if n-1 not in s:
cur, length = n, 1
while cur+1 in s:
cur += 1; length += 1
best = max(best, length)
return best
Complexity
- Time: O(n) amortized, Space: O(n)
Advertisement
