8ms C++ solution (O(n) worst case time, O(1) space) (divide and conquer, array instead of hashmap)


  • 1
    A

    Idea is very simple.

    1. Go through the vector and stores in an array whether each integer appears or not.
    2. Go through the array counting the consecutive integers appeared in the initial vector.

    Step 1 is O(n) time and step 2 is O(1) time, and the space is O(1), because the maximum size of the array is INT_MAX-INT_MIN, which is a constant.

    However, this requires a little too much memory in practice. To handle small vectors better, we should split the vector into several vectors with smaller range (<=MAX_RANGE), and put the result together later. To combine the results of two vectors, we need a little more information, e.g. the length of consecutive numbers including the maximum number.

    Time and space complexity doesn't change by this. With splitting, the sum of the numbers of elements in the two vectors is the same as the number of elements of the original vector. Splitting itself costs O(n) time. The maximum number of splitting is O(1), (INT_MAX-INT_MIN)/MAX_RANGE.

    This is O(n) time algorithm both in average and in worst time.

    #include <algorithm>
    #include <cmath>
    class Solution {
    public:
        const int MAX_RANGE = 65535;
        int longestConsecutive(vector<int>& nums) {
            int a[5];
            longestConsecutiveAll(nums,a,a+1,a+2,a+3,a+4);
            return a[0];
        }
        void longestConsecutiveAll(vector<int>& nums, int* any, int* at_min, int* at_max, int* max, int *min){
            // any : length of longest consecutive numbers
            // at_min : length of longest consecutive numbers which contain the minimum
            // at_max : length of longest consecutive numbers which contain the maximum
            // max : maximum
            // min : minimum
            
            *max = *(max_element(nums.begin(),nums.end()));
            *min = *(min_element(nums.begin(),nums.end()));
            long long lmax=*max, lmin = *min;
            if(lmax-lmin>=MAX_RANGE){
                int border = (*max+*min)/2;
                vector<int> first_half, second_half;
                for(auto i:nums)
                    if(i<border) first_half.push_back(i);
                    else second_half.push_back(i);
                int any_[2], at_min_[2], at_max_[2], max_[2], min_[2];
                longestConsecutiveAll(first_half,&any_[0],&at_min_[0],&at_max_[0],&max_[0],&min_[0]);
                longestConsecutiveAll(second_half,&any_[1],&at_min_[1],&at_max_[1],&max_[1],&min_[1]);
                if(max_[0]+1==min_[1]){ //when first_half and second_half are next to each other by, 
                                        //longest consecutive numbers can span between them
                    *any=std::max(std::max(any_[0],any_[1]),at_max_[0]+at_min_[1]);
                    if(any_[0]==max_[0]-min_[0]+1) //when first_half is all consecutive
                        *at_min=at_min_[1]+any_[0];
                    else
                        *at_min=at_min_[0];
                    if(any_[1]==max_[1]-min_[1]+1) //when second_half is all consecutive
                        *at_max=at_max_[0]+any_[1];
                    else
                        *at_max=at_max_[1];
                }else{
                    *any=std::max(any_[0],any_[1]);
                    *at_max=at_max_[1];
                    *at_min=at_min_[0];
                }
                return;
            }
            
            vector<char> n(*max-*min+1,0);
            for(auto i:nums){
                n[i-*min]=1;
            }
            int longest=0;
            bool is_first=true;
            int current=0;
            for(auto i:n){
                if(i){
                    current++;
                }else{
                    if(is_first)*at_min=current;
                    current=0;
                    is_first=false;
                }
                if(current>longest) longest=current;
            }
            *at_max=current;
            *any=longest;
            return;
        }
    };

Log in to reply
 

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