Consider a Hashset. Add entire input to hashset. Take an element check if consecutive elements are present on right and left side of number, while doing remove each entry from hashset. Takes O(n) time and space.

```
import java.util.HashSet;
import java.util.Iterator;
public class Solution {
public int longestConsecutive(int[] num) {
if (num == null || num.length == 0)
return 0;
HashSet<Integer> set = new HashSet<Integer>();
for(int i = 0; i < num.length; i++) {
set.add(num[i]);
}
int maxCount = 0;
while(true) {
int count = 0;
Iterator<Integer> iter = set.iterator();
Integer key = null;
if(iter.hasNext())
key = iter.next();
else
break;
Integer next = key;
while(set.contains(next)) {
count++;
set.remove(next);
next++;
}
Integer prev = key-1;
while(set.contains(prev)) {
count++;
set.remove(prev);
prev--;
}
if(count > maxCount)
maxCount = count;
}
return maxCount;
}
}
```