Given a sequence of n integers a1, a2, ..., an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.
Note: n will be less than 15,000.
Input: [1, 2, 3, 4] Output: False Explanation: There is no 132 pattern in the sequence.
Input: [3, 1, 4, 2] Output: True Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Input: [-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].
The simplest solution is to consider every triplet and check if the corresponding numbers satisfy the 132 criteria. If any such triplet is found, we can return a True value. If no such triplet is found, we need to return a False value.\n\n
Time complexity : . Three loops are used to consider every possible triplet. Here, refers to the size of array.\n
Space complexity : . Constant extra space is used.\n
We can improve the last approach to some extent, if we make use of some observations. We can note that for a particular number chosen as 2nd element in the 132 pattern, if we don\'t consider (the 3rd element) for the time being, our job is to find out the first element, () which is lesser than .\n
Now, assume that we have somehow found a pair. Our task now reduces to finding out a (, which falls in the range . Now, to maximize the likelihood of a falling in this range, we need to increase this range as much as possible.\n
Since, we started off by fixing a , the only option in our hand is to choose a minimum value of given a particular . Once, this pair , has been found out, we simply need to traverse beyond the index to find if a exists for this pair satisfying the 132 criteria.\n
Based on the above observations, while traversing over the array choosing various values of , we simultaneously keep a track of the minimum element found so far(excluding ). This minimum element always serves as the for the current . Thus, we only need to traverse beyond the index to check the \'s to determine if any of them satisfies the 132 criteria.\n\n
Time complexity : . Two loops are used to find the pairs. Here, refers to the size of array.\n
Space complexity : . Constant extra space is used.\n
As discussed in the last approach, once we\'ve fixed a pair, we just need to determine a which falls in the range . Further, to maximize the likelihood of any arbitrary falling in this range, we need to try to keep this range as much as possible. But, in the last approach, we tried to work only on . But, it\'ll be a better choice, if we can somehow work out on as well.\n
To do so, we can look at the given array in the form of a graph, as shown below:\n
From the above graph, which consists of rising and falling slopes, we know, the best qualifiers to act as the pair, as discussed above, to maximize the range , at any instant, while traversing the array, will be the points at the endpoints of a local rising slope. Thus, once we\'ve found such points, we can traverse over the array to find a satisfying the given 132 criteria.\n
To find these points at the ends of a local rising slope, we can traverse over the given array. While traversing, we can keep a track of the minimum point found after the last peak().\n
Now, whenever we encounter a falling slope, say, at index , we know, that was the endpoint of the last rising slope found. Thus, we can scan over the indices(k>i), to find a 132 pattern.\n
But, instead of traversing over to find a satisfying the 132 pattern for every such rising slope, we can store this range (acting as ) in, say an array.\n
While traversing over the array to check the rising/falling slopes, whenever we find any rising slope, we can keep adding the endpoint pairs to this array. At the same time, we can also check if the current element falls in any of the ranges found so far. If so, this element satisfies the 132 criteria for that range.\n
If no such element is found till the end, we need to return a False value.\n\n
Time complexity : . We traverse over the array of size once to find the slopes. But for every element, we also need to traverse over the to check if any element falls in any range found so far. This array can contain atmost pairs, in the case of an alternate increasing-decreasing sequence(worst case e.g.
[5 6 4 7 3 8 2 9]).
Space complexity : . array can contain atmost pairs, in the worst case(alternate increasing-decreasing sequence).\n
In Approach 2, we found out corresponding to a particular directly without having to consider every pair possible in to find this pair. If we do some preprocessing, we can make the process of finding a corresponding to this pair also easy.\n
The preprocessing required is to just find the best value corresponding to every value. This is done in the same manner as in the second approach i.e. we find the minimum element found till the element which acts as the for the current . We maintain thes values in a array. Thus, now refers to the best value for a particular .\n
Now, we traverse back from the end of the array to find the \'s. Suppose, we keep a track of the values which can potentially satisfy the 132 criteria for the current . We know, one of the conditions to be satisfied by such a is that it must be greater than . Or in other words, we can also say that it must be greater than for a particular chosen.\n
Once it is ensured that the elements left for competing for the are all greater than (or ), our only task is to ensure that it should be lesser than . Now, the best element from among the competitors, for satisfying this condition will be the minimum one from out of these elements.\n
If this element, satisfies , we\'ve found a 132 pattern. If not, no other element will satisfy this criteria, since they are all greater than or equal to $ and thus greater than or equal to as well.\n
To keep a track of these potential values for a particular considered currently, we maintain a on which these potential \'s satisfying the 132 criteria lie in a descending order(minimum element on the top). We need not sort these elements on the , but they\'ll be sorted automatically as we\'ll discuss along with the process.\n
After creating a array, we start traversing the array in a backward manner. Let\'s say, we are currently at the element and let\'s also assume that the is sorted right now. Now, firstly, we check if . If not, we continue with the element and the remains sorted. If not, we keep on popping the elements from the top of the till we find an element, such that, (or ).\n
Once the popping is done, we\'re sure that all the elements pending on the are greater than and are thus, the potential candidates for satisfying the 132 criteria. We can also note that the elements which have been popped from the , all satisfy .\n
Since, in the array, , for every , these popped elements also satisfy , for all . Thus, they are not the potential candidates for even the preceding elements. Even after doing the popping, the remains sorted.\n
After the popping is done, we\'ve got the minimum element from amongst all the potential \'s on the top of the (as per the assumption). We can check if it is greater than to satisfy the 132 criteria(we\'ve already checked ). If this element satisfies the 132 criteria, we can return a True value. If not, we know that for the current , . Thus, the element could be a potential value, for the preceding .\n
Thus, we push it over the . We can note that, we need to push this element on the only when it didn\'t satisfy . Thus, . Thus, even after pushing this element on the , the remains sorted. Thus, we\'ve seen by induction, that the always remains sorted.\n
Also, note that in case , we don\'t push onto the . This is because this isn\'t greater than even the minimum element lying towards its left and thus can\'t act as in the future.\n
If no element is found satisfying the 132 criteria till reaching the first element, we return a False value.\n
The following animation better illustrates the process.\n
Time complexity : . We travesre over the array of size once to fill the array. After this, we traverse over to find the . During this process, we also push and pop the elements on the . But, we can note that atmost elements can be pushed and popped off the in total. Thus, the second traversal requires only time.\n
Space complexity : . The can grow upto a maximum depth of . Furhter, array of size is used.\n
In the last approach, we\'ve made use of a separate to push and pop the \'s. But, we can also note that when we reach the index while scanning backwards for finding , the can contain atmost elements. Here, refers to the number of elements in array.\n
We can also note that this is the same number of elements which lie beyond the index in array. We also know that these elements lying beyond the index won\'t be needed in the future ever again. Thus, we can make use of this space in array instead of using a separate . The rest of the process can be carried on in the same manner as discussed in the last approach.\n
We can try to go for another optimization here. Since, we\'ve got an array for storing the potential values now, we need not do the popping process for a to find an element just larger than from amongst these potential values.\n
Instead, we can make use of Binary Search to directly find an element, which is just larger than in the required interval, if it exists. If such an element is found, we can compare it with to check the 132 criteria. Otherwise, we continue the process as in the last approach.\n\n
Time complexity : . Filling array requires time. The second traversal is done over the whole array of length . For every current we need to do the Binary Search, which requires . In the worst case, this Binary Search will be done for all the elements, and the required element won\'t be found in any case, leading to a complexity of .\n
Space complexity : . array of size is used.\n
In the last approach, we\'ve seen that in the worst case, the required element won\'t be found for all the elements and thus Binary Search is done at every step increasing the time complexity.\n
To remove this problem, we can follow the same steps as in Approach 4 i.e. We can remove those elements(update the index ) which aren\'t greater than (). Thus, in case no element is larger than the index reaches the last element.\n
Now, at every step, only will be added and removed from consideration in the next step, improving the time complexity in the worst case. The rest of the method remains the same as in Approach 4.\n
This approach is inspired by @fun4leetcode\n\n
Time complexity : . We travesre over the array of size once to fill the array. After this, we traverse over to find the . Atmost elements can be put in and out of the array in total. Thus, the second traversal requires only time.\n
Space complexity : . array of size is used.\n
Analysis written by: @vinod23\n