c++ O(1) space O(n) time single pass solution 23ms


  • 0
    O

    All you need to do is to maintain two interval's edge.
    One is [current min, max from right of current min]. The other is [min from left of current max, current max]. Andy number falls into one of these interval, we return true.
    It is not very tricky to maintain. You could understand it easily from the code below.

    bool find132pattern(vector<int>& nums) {
        if (nums.size() < 3)
            return false;
        int curmin, curminMax, curmax, curmaxMin;
        curmin = curminMax = curmax = curmaxMin = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] < curmin) {
                curmin = curminMax = nums[i];
            } else if (nums[i] > curmax) {
                curmax = curminMax = nums[i];
                curmaxMin = curmin;
            } else {
                if (nums[i] > curmin && curminMax > nums[i])
                    return true;
                if (nums[i] > curmaxMin && curmax > nums[i])
                    return true;
                if (nums[i] > curminMax)
                    curminMax = nums[i];                
            }
        }
        return false;
    }

  • 0
    H

    Try [90, 100, 50, 70, 20, 40, 10, 51], it should return true but your code returned false.

    It seems that there isn't an algorithm which can solve the problem in O(n) time.


Log in to reply
 

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