Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
YouTube
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Last updated
Was this helpful?
Was this helpful?
/**
* Time complexity : O(NlogN)
* Space complexity : O(N)
*/
class Solution {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Arrays.sort(nums);
int longestStreak = 1;
int currentStreak = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i-1]) {
if (nums[i] == nums[i-1]+1) {
currentStreak++;
} else {
longestStreak = Math.max(longestStreak, currentStreak);
currentStreak = 1;
}
}
}
return Math.max(longestStreak, currentStreak);
}
}/**
* Time complexity : O(N)
* Space complexity : O(N)
*/
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet();
for(int num: nums) {
set.add(num);
}
int maxCount = 0, processedCount = 0;
for(int num: nums) {
if(!set.contains(num-1)) {
int count = 0;
while(set.contains(num)) {
count++;
num++;
processedCount++;
}
maxCount = Math.max(maxCount, count);
}
if(processedCount == nums.length) {
break;
}
}
return maxCount;
}
}