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