My C++ 8 ms solution using O(logn) Longest Increasing Subsequence


  • 0
    S
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            int n= nums.size();
            if(n<3) return false;
            int arr[3], len=0;
            arr[0] = nums[0];
            for(int i=1; i<n; i++){
                if(nums[i] <= arr[0])
                    arr[0] = nums[i];
                else if(nums[i] > arr[len])
                    arr[++len] = nums[i];
                else if(nums[i] != arr[len] && nums[i]> arr[len-1])
                    arr[len] = nums[i];
                if(len ==2)
                    return true;
            }
            return false;
        }
    };

  • 0
    C

    Should the time complexity be O(n) instead of O(lg(n))?


  • 0
    S

    Yep it is O(n) in this case, however if the longest increasing subsequence length to be found is more than 3 then it becomes O(nlogn)


Log in to reply
 

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