Description Link to heading

456. 132 Pattern (Medium)

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 * 10⁵
  • -10⁹ <= nums[i] <= 10⁹

Solution Link to heading

We can enumerate i to find (j, k) that meets the requirements.

Greedy Algorithm: we need to find the maximum nums[k] that satisfies the requirements. Since k > j, we can traverse the array from back to front.

Denote first = nums[i], second = nums[j], third = -INT_MAX， we can use a monotone stack whose elements decrease from bottom to top to simulate the process.

  • If the stack is empty, we push the element into the stack and don’t update third;
  • If the element to be pushed into the stack is greater than the elemment in the top, we pop the element at the top(if the element popped is larger than third ,we update third), until the stack is empty or the element to be pushed is less than the element at the top;
  • If the element to push is less than the element in the top, we compare the element with third, if the element is less than third, we find the answer, otherwise, we push the element to the stack.

Code Link to heading 

class Solution {
  public:
    bool find132pattern(vector<int> &nums) {
        int first = nums[0], second = nums[nums.size() - 1], third = -INT_MAX;
        int i = 0;
        stack<int> stk; 
        stk.push(nums[nums.size() - 1]);
        for (int r = nums.size() - 2; r >= 0; r--) {
            if (nums[r] < stk.top()) {
                // if (stk.top() > third) {
                if (nums[r] < third) {
                    return true;
                    // }
                }
                stk.push(nums[r]);
            } else if (nums[r] == stk.top()) {
                stk.push(nums[r]);
            } else {
                while (!stk.empty() && nums[r] > stk.top()) {
                    third = std::max(stk.top(), third);
                    stk.pop();
                }
                stk.push(nums[r]);
            }
        }
        return false;
    }
};