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

  • 0
    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]) )
                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.
                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.