[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.

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)$
• 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.

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)$
• 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.

 // 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)$
• 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.

 // 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)$
• 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. 😉😃💗