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


  • -5
    B

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


  • 0
    D

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


Log in to reply
 

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