LeetCode’s 132 Pattern Explained
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.
Example 1:
Input: [1, 2, 3, 4]Output: FalseExplanation: There is no 132 pattern in the sequence.
Example 2:
Input: [3, 1, 4, 2]Output: TrueExplanation: There is a 132 pattern in the sequence: [1, 4, 2].
Please try this on your own before reading ahead.
In the 132 pattern, we observe that the the numbers at index i, j and k… k is always more than both i and j. So one check we definitely need to do is:
ai < ak && aj < ak
Then let’s see if it makes sense to store a minimum array of the minimum number up till all indexes.
Input: [3, 1, 4, 2]minArr: [3, 1, 1, 1]At index 0, the minimum number is the only number 3.
At index 1, the minimum number is the minimum of minArr[0] and input[1]. Which is 1.
At index 2, the minimum number is the minimum of minArr[1] and input[2]. Which is 1 again.
...
Now that we know at every index, if there is a number lower than it before it in sequence, we can start the main logic of going through the inputs and finding an ak which satisfies our requirement.
So for every number we iterate over, we should be able to compare it with a number it is greater than on the left and on the right. We have sorted the left part using our minArr, where we can just use, minArr[i-1] as the number on the left that is less than the number in context.
int left = minArr[i-1];One way to get hold for the numbers on the right of a number in the sequence is if we start iterating from the right.
Now we need to consider if there is a data structure which can return us a number lower than num efficiently. And for that, we have TreeSet!
And this is how the final code looks like:
Now for the worst case space complexity, the tree’s space would be n, where n is the size of the input array. And that of the minArr we used is also n.
The time complexity of the 2 loops is n since each of them would be executed n times. Also, since tree.lower(k) is of O(log n). Therefore the total time complexity is O(nlog n).
Hope this helps! Happy Coding!!
