Share my O(n)O(1) c++ solution with explanation


  • -1
    A
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            int n = nums.size();
            if (n<3) return false;
        
            //1.find firt a & b in increasing order.
            int a = nums[0], b, c, i = 1;
            while (i < n) {
                b = nums[i++];
                if (b > a) break;
                a = b;
            }
            if (i == n) return false;
            
            c = nums[i];
            if (c > b) return true;
        
            while (++i<n) {
                //2. always keep a and b as smaller as posible in increasing order
                if (c<a && nums[i] < b && nums[i] > c) {
                    if (i + 1 == n) return false;
                    a = c;
                    b = nums[i];
                    c = nums[i + 1];
                }
                else if (c>a && c<b) {
                    b = c;
                    c = nums[i];
                }
                else {
                    c = nums[i];
                }
        
                //3. if there is a number greater than b , than we find the triplet
                if (c > b) return true;
            }
        
            return false;
        }
    };

Log in to reply
 

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