By Long Luo

Here are 4 approaches to solve this problem in Java: BF $O(n^3)$, BF $O(n^2)$, TreeMap, Monotonic Stack.

# BF O(n^3)

It’s easy to use 3 loops to find $3$ elements which is $132$ pattern, but the time complexity is $O(n^3)$, so it wouldn’t accepted as TLE!

## Analysis

• Time Complexity: $O(n^3)$.
• Space Complexity: $O(1)$.

# BF O(n^2)

Noticed that $\textit{nums}[j]$ is the peak of the $3$ elements, suppose the current element is $\textit{nums}[j]$, we have to find the element $\textit{nums}[k]$ that is smaller than $\textit{nums}[j]$ after $j$, and the element $\textit{nums}[i]$ that is smaller than $\textit{nums}[k]$ before $j$.

1. Scan left from $j$ to $0$, $0 \le i \lt j$, whether there is $\textit{nums}[i] < \textit{nums}[j]$, update the mininum $\textit{leftMin}$;

2. Scan right from $j$ to the end, $j + 1 \le k \lt len$, whether there is $\textit{nums}[k] < \textit{nums}[j]$, update the maxinum $\textit{rightMax}$;

3. If exists and $\textit{leftMin} < \textit{rightMax}$, return true.

Let’s coding it.

## Analysis

• Time Complexity: $O(n^2)$.
• Space Complexity: $O(1)$.

# TreeMap

Method 2 is $O(n^2)$. With extra $O(n)$ space to store the elements of the array, we can reduce the time complexity to $O(n)$.

We have to maintain all the values of the array in the right of $j$. As we have determined $nums[i]$ and $\textit{nums}[j]$, we only need to query the smallest element $\textit{nums}[k]$ in the sorted set which is strictly larger than $\textit{nums}[i]$.

Then if $\textit{nums}[k] < \textit{nums}[j]$, which means we have found the $3$ elements of $132$ pattern.

## Analysis

• Time Complexity: $O(nlogn)$.
• Space Complexity: $O(n)$.

# Monotonic Stack

We can use a stack to store the element of the array from the back to front, find $\textit{nums}[k]$ in the stack, and then continue to scan forward to find $\textit{nums}[i]$.

The stack must store elements with a larger index and a smaller value than $\textit{nums}[j]$.

The process is like this:

1. Scanning from the back to the front, if the current element $\textit{nums}[i]$ is larger than the top of the stack, which means $\textit{nums}[i]$ may be the $\textit{nums}[j]$ we are looking for;

2. Pop all the elements in the stack that are smaller than it. These elements are the the $\textit{nums}[k]$, and the last pop-up is the maximum qualified $\textit{nums}[k]$.

3. If this $\textit{nums}[k]$ is larger than the $\textit{nums}[i]$ scanned forward, we find the answer.

## Analysis

• Time Complexity: $O(n)$.
• Space Complexity: $O(n)$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗