132 Pattern Problem


Description

LeetCode Problem 456.

Given an arrayof 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:

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

Example 2:

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

Example 3:

1
2
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^5
  • -10^9 <= nums[i] <= 10^9


Sample C++ Code

The problem is to find a subsequence (s1, s2, s3) such that s1 < s3 < s2.

We can start from the end, and search for pair (s2, s3) such that s2 > s3. We keep track of highest value of s3 for each valid (s2 > s3) pair while searching for a valid s1 candidate to the left. Once we encounter any number on the left that is smaller than the largest s3 we have seen so far, we know we find a valid subsequence.

We use a stack to keep track of the largest valid s3 value.

  1. As we scan from right to left, each time we have a number greater than the top of the stack, it is a potential s2. We then pop out all the numbers that are smaller than this number. The numbers that are popped out are candidates for s3.
  2. We keep track of the maximum of such s3, which is always the most recently popped number from the stack.
  3. Once we encounter any number smaller than s3, we find a s1. Then we find a valid subsequence s1, s2, s3. (As the algorithm ensures that for the s3 we store, there is a valid s2 for it. Thus, if we find a number that is smaller than the stored s3, we are done. Based on this reason, we only need to store the max s3 we found.)

Example:

1
2
3
4
5
i = 6, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = None, Stack = Empty
i = 5, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 7, S3 candidate = None, Stack = [9]
i = 4, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 10, S3 candidate = None, Stack = [9,7]
i = 3, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 9, S3 candidate = 9, Stack = [10]
i = 2, nums = [ 9, 11, 8, 9, 10, 7, 9 ], S1 candidate = 8, S3 candidate = 9, Stack = [10,9] We have 8<9, sequence (8,10,9) found!

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
        bool find132pattern(vector<int>& nums) {
        int s3 = INT_MIN;
        stack<int> st;
        for(int i = nums.size()-1; i >= 0; i --){
            if (nums[i] < s3) 
                return true;
            else 
                while (!st.empty() && nums[i] > st.top()) { 
                    s3 = st.top(); 
                    st.pop(); 
                }
            st.push(nums[i]);
        }
        return false;
    }
};




Related Posts

Walking Robot Simulation Problem

LeetCode 874. A robot on an infinite XY-plane starts at...

Valid Mountain Array Problem

LeetCode 941. Given an array of integers arr, return true...

Sum Of Even Numbers After Queries Problem

LeetCode 985. You are given an integer array nums and...

Partition Array Into Disjoint Intervals Problem

LeetCode 915. Given an integer array nums, partition it into...

Monotonic Array Problem

LeetCode 896. An array is monotonic if it is either...

Maximize Distance To Closest Person Problem

LeetCode 849. You are given an array representing a row...