334.increasing-triplet-subsequence.md

334. Increasing Triplet Subsequence

Iteration

We precalculate the minimum and maximum of the array to find the increasing triplet subsequence. For minArray[i], it represents the minimum number from 0 to i, and maxArray[i] represents the maximum number from i to n - 1. Then we iterate the each element as the second number of the triplet, and check if the number is between the previous minimum and next maximum.

fun increasingTriplet(nums: IntArray): Boolean {
    if (nums.size < 3) return false
    val n = nums.size
    val minArray = IntArray(n)
    val maxArray = IntArray(n)

    minArray[0] = nums[0]
    maxArray[n - 1] = nums[n - 1]
    for (i in 1 until n) {
        minArray[i] = minOf(minArray[i - 1], nums[i])
    }
    for (iin n - 2 downTo 0) {
        maxArray[i] = maxOf(maxArray[i + 1], nums[i])
    }

    for (i in 1 until n - 1) {
        if (minArray[i - 1] < nums[i] && nums[i] < maxArray[i + 1]) return true
    }
    return false
}

Greedy

We iterate the array and keep track of the smallest and second smallest number. We choose first and second greedily to be as small as possible:

• We compare third with first first, because we want to keep first as small as possible, if we have updated first, then we don't update second. (Avoid by using if-else statement)
• We update second only when first < third < second, it only gets updated when there exists first that comes before it.

if (third <= first) {
    ...
} else if (third <= second) {
    // We update `second` only when `first < third < second`
}

Please note that we don't have to shift first and second when we find out the smaller number than first and second, because we only care about the relative order of the numbers. The following code is wrong:

if (third < first) {
    second = first
    first = third
}

Failed case: [5, 1, 6], first will be 1 and second will be 5, 6 will return true but that is the wrong answer.

Or [3, 5, 1]

fun increasingTriplet(nums: IntArray): Boolean {
    var first = Int.MAX_VALUE
    var second = Int.MAX_VALUE
    for (num in nums) {
        // Find the smallest number
        if (num < first) first = num
        // Find the second smallest number
        // We can't simply use `num < second` only, see `[1, 2, 1, 3]`
        else if (first < num && num < second) second = num
        
        if (first < num && second < num) return true
    }
    return false
}

// Or equivalent
fun increasingTriplet(nums: IntArray): Boolean {
    var first = Int.MAX_VALUE
    var second = Int.MAX_VALUE
    for (third in nums) {
        // Equal comparision is necessary, see `[1, 2, 1, 3]`
        if (third <= first) {
            first = third
        } else if (third <= second) {
            second = third
        } else if (first < second && second < third) {
            return true
        }
    }
    return false
}

Failed Cases

1. [1, 2, 1, 3]

# WA
def increasingTriplet(self, nums: List[int]) -> bool:
    first, second = inf, inf
    for num in nums:
        if num < first:
            first = num
        elif num < second: # Not `first < num < second`
            second = num

        if first < second < num:
            return True
    return False