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 ) (i, j, k) ( i , j , k ) such that i < j < k i < j < k i < j < k and n u m s [ i ] < nums [ j ] < nums [ k ] nums[i] < \textit{nums}[j] < \textit{nums}[k] n u m s [ i ] < nums [ j ] < 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 ) O(n^3) O ( n 3 ) , it will TLE , so we need to find a better way.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static boolean increasingTriplet (int [] nums) { if (nums == null || nums.length < 3 ) { return false ; } int len = nums.length; for (int i = 0 ; i < len; i++) { for (int j = i + 1 ; j < len; j++) { for (int k = j + 1 ; k < len; k++) { if (nums[i] < nums[j] && nums[j] < nums[k]) { return true ; } } } } return false ; }
Analysis
Time Complexity : O ( n 3 ) O(n^3) O ( n 3 )
Space Complexity : O ( 1 ) O(1) O ( 1 )
Dynamic Programming
We can also use DP method to solve it.
Let d p [ i ] dp[i] d p [ i ] represents the maximum length of a increasing sequence.
d p [ i ] = { 1 d p [ i ] ≤ d p [ j ] , 0 < j < i d p [ j ] + 1 d p [ i ] > d p [ j ] , 0 < j < i 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}
d p [ i ] = { 1 d p [ j ] + 1 d p [ i ] ≤ d p [ j ] , 0 < j < i d p [ i ] > d p [ j ] , 0 < j < i
We can reduce the time complexity to O ( n 2 ) O(n^2) O ( n 2 ) , but it still will TLE .
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public boolean increasingTriplet (int [] nums) { int len = nums.length; int [] dp = new int [len]; Arrays.fill(dp, 1 ); for (int i = 0 ; i < len; i++) { for (int j = 0 ; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = dp[j] + 1 ; } if (dp[i] >= 3 ) { return true ; } } } return false ; }
Analysis
Time Complexity : O ( n 2 ) O(n^2) O ( n 2 )
Space Complexity : O ( n ) O(n) O ( n )
Two Pointers
When traversing the array nums [ j ] \textit{nums}[j] nums [ j ] , 0 < j < n − 1 0 < j < n − 1 0 < j < n − 1 , if there is an element on the left of nums [ i ] < nums [ j ] \textit{nums}[i] < \textit{nums}[j] nums [ i ] < nums [ j ] , 0 ≤ i < j 0 \le i < j 0 ≤ i < j , and an element on the right of nums [ k ] \textit{nums}[k] nums [ k ] , j < k < l e n j < k < len j < k < l e n .
Therefore, we can maintain the minimum value on the left and the maximum value on the right of each element in the array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 public static boolean increasingTriplet_tp (int [] nums) { if (nums == null || nums.length < 3 ) { return false ; } int len = nums.length; int [] leftMin = new int [len]; leftMin[0 ] = nums[0 ]; for (int i = 1 ; i < len; i++) { leftMin[i] = Math.min(leftMin[i - 1 ], nums[i]); } int [] rightMax = new int [len]; rightMax[len - 1 ] = nums[len - 1 ]; for (int i = len - 2 ; i >= 0 ; i--) { rightMax[i] = Math.max(rightMax[i + 1 ], nums[i]); } for (int i = 0 ; i < len; i++) { if (nums[i] > leftMin[i] && nums[i] < rightMax[i]) { return true ; } } return false ; }
Analysis
Time Complexity : O ( n ) O(n) O ( n )
Space Complexity : O ( n ) O(n) 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 first \textit{first} first and second \textit{second} second , with second > first \textit{second} > \textit{first} second > first , now we have to find the third \textit{third} third number while traversing the array.
The t h i r d third t h i r d number can be as follows:
If third > second \textit{third} > \textit{second} third > second , we have found it and return true directly.
If third < second \textit{third} < \textit{second} third < second && third > first \textit{third} > \textit{first} third > first , we make second = third \textit{second} = \textit{third} second = third , and continue traversing the rest array to find the t h i r d third t h i r d number.
If third < first \textit{third} < \textit{first} third < first , we make first = third \textit{first} = \textit{third} first = third , and then continue to search for the third \textit{third} third .
The trick is here.
You would worry that the first \textit{first} first is now behind the second \textit{second} second . Image if we meet third > second \textit{third} > \textit{second} third > second , we can use the old first \textit{first} first that meets first < second < third \textit{first} < \textit{second} < \textit{third} first < second < third .
We make first = third \textit{first} = \textit{third} first = third , we can select a lower second \textit{second} second and third \textit{third} third because the first \textit{first} first become smaller.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public boolean increasingTriplet (int [] nums) { if (nums == null || nums.length < 3 ) { return false ; } int first = nums[0 ]; int second = Integer.MAX_VALUE; for (int third : nums) { if (third > second) { return true ; } else if (third > first) { second = third; } else { first = third; } } return false ; }
Analysis
Time Complexity : O ( n ) O(n) O ( n )
Space Complexity : O ( 1 ) O(1) 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 . 😉😃💗