456. 132 Pattern

Description

Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].

Return true if there is a 132 pattern in nums, otherwise, return false.

Example 1:

Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.

Example 2:

Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].

Example 3:

Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].

Constraints:

• n == nums.length
• 1 <= n <= 2 * 105
• 109 <= nums[i] <= 109

---

Solutions

Solution 1

Intuition

1, 2, 3, 5, 4, 6, 7

from right to left, store decreased number(like 7, 6, 4), if the number (eg. 5) is not in decreasing order, pop other numbers in stack(which is 4) and make sure it is monotonic stack, besides record the largest number num_j(which is 4). if find other number(num_i) in left smaller than num_j return true, otherwise return false

Code

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        stack<int> stk;
        int num_j = INT_MIN;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums[i] < num_j) return true;
            while (!stk.empty() && nums[i] > stk.top()) {
                num_j = max(num_j, stk.top());
                stk.pop();
            }
            stk.push(nums[i]);
        }
        return false;
    }
};

Complexity

• Time: O(n)
• Space: O(n)

Comments

[Wenqi Jiang]

maybe O(2N)?

[Wenqi Jiang]

Hey, Tony. Thank you for replying. I think the time complexity of monotonic stack is O(n). Because while loop is simply poping stack elements one by one and there can not be more than N elements pushed inside the stack ( every element pushed once ). So even though while loop is nested inside for loop it will not execute more that N times.