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. 😉😃💗