public int longestConsecutive(int[] num) {
int max = 0;
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < nums.length; i++) {
set.add(nums[i]);
}
for (int i = 0; i < nums.length; i++) {
int count = 1;
// look left
int num = nums[i];
while (set.contains(num)) {
count++;
set.remove(num);
}
// look right
num = nums[i];
while (set.contains(++num)) {
count++;
set.remove(num);
}
max = Math.max(max, count);
}
return max;
}
Another accepted Java O(n) solution


It seems to me that in the worst case, this solution is far more than O(n).
Consider the in put are integers from 1 to n.But, this is still a good solution.
=========================================================
It's my mistake. I didn't notice the remove option.
Yes, this is an amortized O(n) solution.