A stupid solution in C++, easily understood


  • 0
    P

    If there is a number which has a smaller left number and a bigger right number, return true else return false.

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) 
        {
            int nSize = nums.size();
            if(nSize<3)
                return false;
                
            vector<bool> hasLeft(nSize, false);
            vector<bool> hasRight(nSize, false);
            
            for(int i=0; i<nSize; i++)
                for(int j=i; j<nSize; j++)
                    if(nums[i] < nums[j])
                        hasLeft[j] = true;
    
            for(int i=nSize-1; i>=0; i--)
                for(int j=i; j>=0; j--)
                    if(nums[j] < nums[i])
                        hasRight[j] = true;
                        
            for(int i=0; i<nSize; i++)
                if(hasLeft[i] && hasRight[i])
                    return true;
                    
            return false;
        }
    };

  • 0
    D

    Try to populate the two arrays hasLeft and hasRight in O(n) time.


  • 0
    P

    Thank you for your reply. I has added an O(n) version code in the answer.


  • 0
    P

    Add a quicker solution. It's in O(n) time. I think it's a smart solution now.

    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) 
        {
            int nSize = nums.size();
            if(nSize<3)
                return false;
                
            vector<bool> hasLeft(nSize, false);
            vector<bool> hasRight(nSize, false);
            
            for(int i=1, Min=nums[0]; i<nSize; i++)
                if(Min < nums[i])
                    hasLeft[i] = true;
                else
                    Min = nums[i];
    
            for(int i=nSize-2, Max=nums.back(); i>=0; i--)
                if(nums[i] < Max)
                    hasRight[i] = true;
                else
                    Max = nums[i];
                        
            for(int i=0; i<nSize; i++)
                if(hasLeft[i] && hasRight[i])
                    return true;
                    
            return false;
        }
    };

  • 0
    S

    Very easy to understand and I think it's a good solution. Thanks!


  • 0
    P

    Glad to help.


Log in to reply
 

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