Short and clean 6ms O(n) and constant time C++ solution


  • 1
    C

    We can scan over this array from left to right, and our first goal is to establish a pair of nums[i] and nums[j] that satisfy the condition nums[j] > nums[i] where i < j.

    If we now have a nums[k] which is greater than nums[j] we find our triplet. And along the scan, we need to minimize the pair nums[i] and nums[j] as much as possible.

    There are the following cases at each position when we scan.

    1. nums[i] is not established, we need to set nums[i]
    2. nums[j] is not established, we need to set nums[j]
    3. The current nums[k] is smaller than nums[i], we need to update nums[i]
    4. the current nums[k] is smaller than nums[j] but greater than nums[i], we need to update nums[j]

    Operations for case 3, 4 is correct because only by minimizing both nums[i] and nums[j] can we ensure we have better chance to find a nums[k] that is greater than both.

    Since we are looking for increasing order not non-decreasing, we need to skip duplicate if any matches nums[i] and nums[j].

        bool increasingTriplet(vector<int>& nums) {
            int iNum = INT_MAX;
            int jNum = INT_MAX;
            for (int k=0; k<nums.size(); k++) {
                if (nums[k] > jNum) return true;
                if (nums[k] == iNum || nums[k] == jNum) continue;
                if (iNum > nums[k]) {
                    iNum = nums[k];
                } else if (jNum > nums[k]) {
                    jNum = nums[k];
                }
            }
            return false;
        }
    

Log in to reply
 

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