Java O(n) in time and O(n) in space Solution with explanation


  • 0
    J
     public int longestConsecutive(int[] nums) {
            if(nums.length==0) return 0;
            Map<Integer,Integer> map = new HashMap();
            for(int num: nums) 
                map.putIfAbsent(num,num+1);
            int max=0,key,count;
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                key = entry.getKey();
                if(map.containsKey(key-1)) 
                    continue;
                count =1;
                while(map.containsKey(++key))
                    count++;
                max = Math.max(count,max);
            }
            return max;
        }
    

    We create a map to save key as current number and save value as number+1. Building map takes O(n).
    Then we iterate map. If map contains key of (key-1), that means it is in sequence but not the start of it, we ignore this and continue. Otherwise, we iterater map by getting next consecutive key in map, count the length of sequence and do comparison when it reaches the end of sequence. The worst case is every elements has been iterated twice in the second for loop. Therefore, the total time complexity is O(n)
    We only use map as extra space, so it is O(n) as well.


Log in to reply
 

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