Simple easy understand intuitive C++ solution without using INT_MAX. Explained!


  • 0

    Thought: I use min1, max1 to record the starting point and end point of increasing subarray of length two. They are initialized to both -1 as an indicator if such array ever exists. Thus, I can avoid the usage of INT_MAX.

    So, starting from position 1, when we encounter a new number, we have the following situations:

    1. It’s the global min. Minimum so far

    2. Length of two subarray already exists(max1 > 0), and this number is greater than nums[max1], so answer is found.

    3. If all above didn’t happen, and we found that current number is actually greater than global min, so they become the length of two increasing sub-array. Please note that this could be 1) the first length of 2 array or 2) a better length of 2 candidate array. The new nums[max1] should be less or equal to the prior nums[max1] if it exists. Why? Otherwise, we should already return true in scenario 2 already right?

    4. Done. Return false if true never happens :) Hope this helps.

    As an example:

    e.g. 6.......5.......3.......5.......5.......4.......2.......5

    ......................min1 max1

    ......................min1...................max1 (better candidate min1, and max1)

    .................................................................found (6 > nums[max1], so [3, 4, 5] satisfies the requirement)

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

Log in to reply
 

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