[LeetCode][334. Increasing Triplet Subsequence] Why Greedy Works?
By Long Luo
This article is the solution Why Greedy Works? of Problem 334. Increasing Triplet Subsequence.
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.
1  public static boolean increasingTriplet(int[] nums) { 
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.
1  public boolean increasingTriplet(int[] nums) { 
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.
1  // time: O(n) space: O(n) 
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:

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

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.

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

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}$.

We make $\textit{first} = \textit{third}$, we can select a lower $\textit{second}$ and $\textit{third}$ because the $\textit{first}$ become smaller.
1  // time: O(n) space: O(1) 
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. 😉😃💗