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