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
}
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
withfirst
first, because we want to keepfirst
as small as possible, if we have updatedfirst
, then we don't updatesecond
. (Avoid by usingif-else
statement) - We update
second
only whenfirst < third < second
, it only gets updated when there existsfirst
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 be1
andsecond
will be5
,6
will returntrue
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
}
[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