By Long Luo

Here are 6 approaches to solve this problem in Java.

# 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 timeout.

## Analysis

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

# BF O(n^2)

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

1. Scan left from $j$ to $0$, $0 <= i < j$, whether there is $num[i] < nums[j]$, update the mininum $leftMin$;

2. Scan right from $j$ to the end, $j + 1 <= k < len$, whether there is $num[k] < nums[j]$, update the maxinum $rightMax$;

3. If exists and $leftMin < 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 $nums[j]$, we only need to query the smallest element $nums[k]$ in the sorted set which is strictly larger than $nums[i]$.

Then if $nums[k] < 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 $nums[k]$ in the stack, and then continue to scan forward to find $nums[i]$.

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

The process is like this:

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

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

3. If this $num[k]$ is larger than the $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. 😉😃💗