//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;

}