Java 13ms solution with Time O(n), Space O(n)


  • 0
    L
    public class Solution {
        public int longestConsecutive(int[] nums) {
            if(nums == null || nums.length == 0) return 0;
            if(nums.length == 1) return 1;
    
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
            //Initial map
            for(int x: nums) map.put(x, 1/*init length=1*/);
    
            Integer next;
            int max=0, len, nextLen;
            for( int i=0; i<nums.length; i++) {
                if(!map.containsKey(nums[i]) )
                    continue;
    
                next = nums[i];
                len = map.get(next);
                //Check whether the next smaller number exist or not.
                while( map.containsKey(--next)) {
                    nextLen = map.get(next);    //get next.length
                    len += nextLen;             //set len+=next.length
                    map.remove(next);           //Remove the middle item in the link to avoid calculate it again.
    
                    if( nextLen >1)     //Stop when the next length calculated before.
                        break;
                }
    
                map.put(nums[i],len);
                max = Math.max(max, len);
            }
    
            return max;
        }
    }
    

Log in to reply
 

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