Easy 8ms O(n) solution in C++


  • 0
    A
    class Solution {
    public:
        bool increasingTriplet(vector<int>& nums) {
            // pruning 
            int n = nums.size();
            if (n < 3) return false;
            vector<int> tracker; tracker.reserve(4); 
            for (int idx = 0; idx < n ; ++idx){
                if (tracker.size() == 0) tracker.push_back(nums[idx]);
                else if (tracker.size() == 1){
                    if (tracker[0] >= nums[idx]) tracker[0] = nums[idx];
                    else tracker.push_back(nums[idx]);
                }
                else{
                    if (tracker[1] < nums[idx]) return true;
                    else if (tracker[0] < nums[idx] && tracker[1] >= nums[idx]) tracker[1] = nums[idx];
                    else if (tracker[0] >= nums[idx]) tracker[0] = nums[idx];
                }
            }
            return false;
        }
    };

Log in to reply
 

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