My less than 5m solution with O(1) space and O(nlogn) time.


  • 0
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        //sort array take O(nlog(n)) time
        Arrays.sort(nums);
        int index = 1;
        //"remove" duplicate
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1] ) {
                nums[index++] = nums[i];
            }
        }
        int j = 0;
        int max = 0;
       //now index is the index where noduplicate ends
       // idea is, iterator through array, if find non consecutive number, break, and update i to the next index where it breaks.
        for (int i = 0; i < index; i++) {
            int len = 0;
            j = i;
            while (j + 1 < index) {
                if (nums[j] == nums[j+1] -1) {
                    j++;
                } else {
                    break;
                }
            }
            //if end of the array, need to add 1.
            if (j + 1 == index - 1 && nums[j] + 1 == nums[j+1]) {
                len = j + 1 - i + 1;
            } else {
                len = j - i + 1;
            }
            max = Math.max(len, max);
            //you dont have to check the previous numbers anymore.
            i = j;
        }
        return max;
    }

Log in to reply
 

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