# LeetCode’s 132 Pattern Explained

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence a**i**, a**j**, a**k** such that **i** < **j** < **k** and a**i** < a**k** < a**j**. 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:

a**i** < a**k** && a**j** < a**k**

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 a**k **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!!