Problem
Given an unsorted array of integers, find the length of the longest consecutive elements sequence in O(n).
Example
Input: [100,4,200,1,3,2]
Output: 4
Longest is [1,2,3,4].Solution
Hash set. For each number that has no predecessor in the set, count how far the sequence runs.
def longest_consecutive(nums):
s = set(nums)
longest = 0
for n in s:
if n - 1 not in s:
curr = n
length = 1
while curr + 1 in s:
curr += 1
length += 1
longest = max(longest, length)
return longestfunction longestConsecutive(nums) {
const set = new Set(nums);
let longest = 0;
for (const n of set) {
if (!set.has(n - 1)) {
let curr = n, length = 1;
while (set.has(curr + 1)) { curr++; length++; }
longest = Math.max(longest, length);
}
}
return longest;
}int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int longest = 0;
for (int n : s) {
if (!s.count(n - 1)) {
int curr = n, length = 1;
while (s.count(curr + 1)) { curr++; length++; }
longest = max(longest, length);
}
}
return longest;
}public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) set.add(n);
int longest = 0;
for (int n : set) {
if (!set.contains(n - 1)) {
int curr = n, length = 1;
while (set.contains(curr + 1)) { curr++; length++; }
longest = Math.max(longest, length);
}
}
return longest;
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
Only start counting from sequence starts (no n-1 in set). This avoids re-counting from middle elements, keeping it O(n) overall.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?