[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)(i, j, k) such that i<j<ki < j < k and nums[i]<nums[j]<nums[k]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(n3)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(n3)O(n^3)
  • Space Complexity: O(1)O(1)

Dynamic Programming

We can also use DP method to solve it.

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

dp[i]={1dp[i]dp[j],0<j<idp[j]+1dp[i]>dp[j],0<j<idp[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(n2)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(n2)O(n^2)
  • Space Complexity: O(n)O(n)

Two Pointers

When traversing the array nums[j]\textit{nums}[j], 0<j<n10 < j < n − 1, if there is an element on the left of nums[i]<nums[j]\textit{nums}[i] < \textit{nums}[j], 0i<j0 \le i < j, and an element on the right of nums[k]\textit{nums}[k], j<k<lenj < 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
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
 // time: O(n) space: O(n)
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)
  • Space Complexity: 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} and second\textit{second}, with second>first\textit{second} > \textit{first}, now we have to find the third\textit{third} number while traversing the array.

The thirdthird number can be as follows:

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

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

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

The trick is here.

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 // time: O(n) space: O(1)
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)
  • Space Complexity: 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. 😉😃💗