By Long Luo

# Intution

We can easily find that whether there exists a triple of indices $(i, j, k)$ such that $i < j < k$ and $nums[i] < \textit{nums}[j] < \textit{nums}[k]$ only traversing the array once, but the problem is how to make our mind into algorithms.

# Brute Force

It’s easy to use Brute Force way to solve this problem, but the time complexity is $O(n^3)$, it will TLE, so we need to find a better way.

## Analysis

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

# Dynamic Programming

We can also use DP method to solve it.

Let $dp[i]$ represents the maximum length of a increasing sequence.

$dp[i] = \begin{cases} 1 & dp[i] \le dp[j], 0 < j < i \\ dp[j] + 1 & dp[i] > dp[j], 0 < j < i \end{cases}$

We can reduce the time complexity to $O(n^2)$, but it still will TLE.

## Analysis

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

# Two Pointers

When traversing the array $\textit{nums}[j]$, $0 < j < n − 1$, if there is an element on the left of $\textit{nums}[i] < \textit{nums}[j]$, $0 \le i < j$, and an element on the right of $\textit{nums}[k]$, $j < k < len$.

Therefore, we can maintain the minimum value on the left and the maximum value on the right of each element in the array.

## Analysis

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

# Greedy

We can easily know that we can find the answer with just traverse the array once.

Assuming that we already have two numbers $\textit{first}$ and $\textit{second}$, with $\textit{second} > \textit{first}$, now we have to find the $\textit{third}$ number while traversing the array.

The $third$ number can be as follows:

1. If $\textit{third} > \textit{second}$, we have found it and return true directly.

2. If $\textit{third} < \textit{second}$ && $\textit{third} > \textit{first}$, we make $\textit{second} = \textit{third}$, and continue traversing the rest array to find the $third$ number.

3. If $\textit{third} < \textit{first}$, we make $\textit{first} = \textit{third}$, and then continue to search for the $\textit{third}$.

The trick is here.

1. You would worry that the $\textit{first}$ is now behind the $\textit{second}$. Image if we meet $\textit{third} > \textit{second}$, we can use the old $\textit{first}$ that meets $\textit{first} < \textit{second} < \textit{third}$.

2. We make $\textit{first} = \textit{third}$, we can select a lower $\textit{second}$ and $\textit{third}$ because the $\textit{first}$ become smaller.

## Analysis

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

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