# Java O(n) solution (sorry it is still very slow)

• //use 3 hashmaps and it is O(N) since get,put,containsKey are all average O(1) for hashmap
//idea is to track the intervals and try to attach new elements to them

public int longestConsecutive(int[] num) {
if(num==null || num.length==0)
return 0;
Map<Integer, Integer> visited=new HashMap<Integer, Integer>();
Map<Integer, Integer> low=new HashMap<Integer, Integer>();
Map<Integer, Integer> high=new HashMap<Integer, Integer>();
int maxLen=1;
for(int v : num)
{
if(visited.containsKey(v))
continue;
visited.put(v,v);
if(!low.containsKey(v+1))
{
if(!high.containsKey(v-1))
{
low.put(v,v);
high.put(v,v);
}
else
{
int w=high.get(v-1); //low end of a known interval
low.put(w,v);
high.remove(v-1);
high.put(v,w);
if(maxLen<(v-w+1))
maxLen=(v-w+1);
}
}
else
{
if(!high.containsKey(v-1))
{
int w=low.get(v+1); //high end of a known interval
high.put(w,v);
low.remove(v+1);
low.put(v,w);
if(maxLen<(w-v+1))
maxLen=(w-v+1);
}
else
{
int x=low.get(v+1); //high end of a known interval
int y=high.get(v-1); //low end of a known interval
maxLen=Math.max(maxLen,x-y+1);
low.put(y,x);
high.put(x,y);
low.remove(v+1); //not necessary
high.remove(v-1);//not necessary
}
}
}
return maxLen;
}

• Sorry but this is unreadable. Could you format your code so we can learn from it?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.