My one pass cpp solution


  • 0
    C
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums)
        {
            if(nums.size() < 3) return false;
            
            int dp[3];
            dp[0] = nums[0];
            
            int inc_subseq_len = 0;
            int id = 0;
            
            while(inc_subseq_len < 2 && ++id < nums.size())
            {
                if(nums[id] <= dp[0])
                {
                    dp[0] = nums[id];
                    continue;
                }
                
                if(nums[id] > dp[inc_subseq_len])
                {
                    dp[++inc_subseq_len] = nums[id];
                    continue;
                }
                
                for(int i=inc_subseq_len-1; i>=0; i--)
                {
                    if(nums[id] > dp[i])
                        dp[i+1] = nums[id];
                }
            }
            
            return inc_subseq_len >= 2;
        }
    };

Log in to reply
 

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