C++ o(nlogn) solution with explainations, 4ms


  • 13
    A

    The solution is building a ladder for numbers, with level number labels the max sequence for all numbers on that level;
    when a new number comes in, compare it with the smallest number in each level--starting from the highest level, if larger than the (smallest) number in that level, the new number is insert into level+1
    else compare with the smallest number in second highest level ...

    e.g. [10, 9, 2, 5, 3, 7, 101, 18]

    level: numbers

    4: 101, 18

    3: 7

    2: 5, 3

    1: 10, 9, 2

    Since we only use the smallest number in each level, we do not need save the others, an extra vector<int> of size m(=max level) would be enough

    int lengthOfLIS(vector<int>& nums) {
        vector<int> ladder(1);
        if(nums.empty()) return 0;
        ladder[0]=nums[0];
        for(int i=1; i<nums.size(); ++i){
            int m=int(ladder.size());
            bool foundless=false;
            for(int j=m-1;j>=0;--j){
                if(nums[i] > ladder[j]){
                    if(j+1==ladder.size()){
                        ladder.push_back(nums[i]);
                    }
                    else{
                        ladder[j+1]=min(ladder[j+1],nums[i]);
                    }
                    foundless=true;
                    break;
                }
            }
            if(!foundless) ladder[0]=min(ladder[0],nums[i]);
        }
        return ladder.size();
    }

  • 0
    J

    nice solution


  • 0
    J

    Nice solution. But the worst case complexity can be of order n^2. For example consider N size array (N even) of which the even index positions form an ascending array from values {1,2,...,N/2} and the odd index positions form a descending array from the same values. Toward the end of full array, the value of m will be N/2 and at odd index positions, the inner loop would run close to N/2 times until it finds smaller value.


  • 0
    A

    You are right, it'a actually a worst case O(N^2) solution. However since my vector is strictly sorted, we can use binary search to find first smaller number--thus improve it into a o(NlogN) solution


Log in to reply
 

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