128. Longest Consecutive Sequence

Q:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

A:
由于自己很少很少用HashMap, 因此，遇到了这个用2个HashMap 连用的情况，还是很抓瞎的。 花了近3个小时，才弄出来。哎

思想比较简单： for each   val = num[i],  we map val to the key value, where key is the start of Interval, where val lies.( if val does not find ,we insert.)
and in the second HashMap, we map the key to the interval.
步骤如下：
 if val is not found ,
case 1) check if (val -1 ) and (val +1) exist, if it is, then combine these two intervals
case 2) find (val-1),  add val to this left interval , and interval.end++
case 3) find (val+1) , add val to this right interval, and  interval.start--
case 4) val is isolate,  simply add this list.
always update the maxLen of this list.
 代码如下：

public class Solution {
   public int longestConsecutive(int[] num) {
        // map the num[i] value to a key ( used in next HashMap) , which is the start of interval 
        HashMap<Integer, Integer> map2Key = new HashMap<Integer, Integer>();
        // map key value to interval 
        HashMap<Integer, Interval> map2Interval = new HashMap<Integer, Interval>();
        int maxLen = 0;
        for (int i = 0; i < num.length; i++) {
            int val = num[i];
            if(! map2Key.containsKey(val)) {// first time to find value
                int key;// check val -1 and val +1, 
                if(map2Key.containsKey(val -1)  && map2Key.containsKey(val +1)){// val is in middle
                    // merge two list, and delete the val+1 map
                    int keyLow = map2Key.get(val -1);
                    int keyHigh = map2Key.get(val + 1);
                    map2Interval.get(keyLow).end = map2Interval.get(keyHigh).end;
                    //update all the map2Key values
                    for(int j = val; j<= map2Interval.get(keyHigh).end ;j++){
                        map2Key.put(j, keyLow );
                    }
                    map2Interval.remove(keyHigh);                    
                    key = keyLow;
                }else if(map2Key.containsKey(val -1)){ // val is at right
                    map2Key.put(val, map2Key.get(val-1));
                    key = map2Key.get(val-1);
                    map2Interval.get(key).end++;
                }else if(map2Key.containsKey(val +1)){
                    map2Key.put(val, map2Key.get(val+1));
                    key = map2Key.get(val + 1);
                    map2Interval.get(key).start--;
                }else{ // the new value is isolate
                    key = val;
                    map2Key.put(val, val);
                    map2Interval.put(key, new Interval(val,val));
                }
                // update maxLen
                maxLen = Math.max(maxLen, map2Interval.get(key).end - map2Interval.get(key).start+1);
            }
        }
        return maxLen;
    }
}

--------------------------第二遍-------------看了网上的，别人的思路了------
 思路如下：----

• Put the number into HashSet, O(n);
• Check the num[] from the first to the last
• get value of num[i],remove it from set, low = num[i]-1; high = num[i]+1;
• check if the low and high are in the set
• if yes. low or high expand 1; remove this number from set
• if no. continue;
• calculate the value of low and high. get longest
• return longest

public class Solution {
   public int longestConsecutive(int[] num) {
        // use only one hashMap
        Set<Integer> set = new HashSet<Integer>();
        
        for(int i = 0; i< num.length;i++)
            set.add(num[i]);
        int maxLength =0;
        for(int i = 0; i< num.length;i++){
            if( !set.contains(num[i]))// it is already find
                continue;
            int low = num[i]-1;
            int high = num[i] +1;
            while(set.contains(low)){
                set.remove(low);
                low--;
            }
            while(set.contains(high)){
                set.remove(high);
                high++;
            }
            maxLength = Math.max(maxLength, high-low -1);
        }
        return maxLength;
    }
} 

----------------------第三遍 -----------------------------
比第二遍的改进就是，  low= num[i] ， 这样就可以同时删除num[i] 这个节点了。



Mistakes:
1:  in case 1, when two list are merged.
     we should point all the val values in the high part of the list,, with their mapping key value to  leftInterval.start


Learned: