Solution by <644367822>


  • 0
    6

    Approach # 1 Brute Force [ Time Limit Exceeded ]

    Algorithm

    For each num of array (index from 1 to n - 1 ), we check whether index i meets such conditions

    1 If it exist a index j (index from 0 to i - 1 ) Satisfies nums[j] < nums[i] - do condition 2 ,else next index i+1 .

    2 If it exist a index k (index from i+1 to n ) Satisfies nums[j] > nums[i] return true ,else next index i+1 .

    In the end ,if i == n return fasle .

    c++

    
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            if( nums.size() < 3) {
                return false ;
            }
            for( int i = 1 ; i < nums.size() - 1 ; i ++ ) {
                bool find = false ;
                for( int j = 0 ; j < i ; j ++ ) {
                    if( nums[j] < nums[i] ) {
                        find = true ;
                        break;
                    }
                }
                if( !find ){
                    continue ;
                }
                for( int k = i + 1 ; k < nums.size() ; k ++ ) {
                    if( nums[k] > nums[i] ) {
                        return true ;
                    }
                }
            }
            return false ;
        }
    };
    
    
    

    Complexity Analysis

    • Time complexity : $O(N^2)$.
    • Space complexity : $O(1)$.

    ####Approach #2 Dynamic Programming [Accepted]

    Algorithm

    We can treat this problem as Longest Increasing Subsequence ,if the length of LIC >= 3 return true .

    c++

    
    
    class Solution {
    public:
       int lengthOfLIS(vector<int>& nums) {
            vector<int> LIS;
            for (int i = 0; i < nums.size(); i++) {
                if (LIS.size() == 0 || LIS[LIS.size() - 1] < nums[i]) {
                    LIS.push_back(nums[i]);
                }
                else {
                    int l = 0, r = LIS.size() - 1;
                    while (l < r) {
                        int m = (l + r) / 2;
                        if (LIS[m] >= nums[i]) {
                            r = m;
                        }
                        else {
                            l = m + 1;
                        }
                    }
                    LIS[l] = nums[i];
                }
            }
            return LIS.size();
        }
        bool increasingTriplet(vector<int>& nums) {
            return lengthOfLIS(nums) >=3;
        }
    };
    
    
    
    

    Complexity Analysis

    • Time complexity : $O(N*logN)$. Binary Search + Dynamic Programming
    • Space complexity : $O(N)$.

    ####Approach #3 Scan and update [ Accepted ]

    Algorithm

    We scan the array from left to right and save the val used to record the first 2 elements of increasing size in an array.

    c++

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            if( nums.size() < 3 ) {
                return false ;
            }
            int a = nums[0] ;
            int b = INT_MAX ;
            for( int i = 0 ; i < nums.size() ; i ++ ) {
                if( nums[i] <= a ) {
                    a = nums[i] ;
                }
                else {
                    if( nums[i] <= b ) {
                        b = nums[i] ;
                    }
                    else {
                        return true ;
                    }
                }
            }
            return false ;
        }
    };
    

    Complexity Analysis

    • Time complexity : $O(N)$.
    • Space complexity : $O(1)$.

Log in to reply
 

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