Increasing Triplet Subsequence

• LeetCode

• Initialize first and second to math.inf
• Iterate through array, for each number num:
  • if num <= first, update num = first
    • Kinda like a greedy approach, first should always have the smallest value
  • elif num <= second, update num = second
    • Likewise, second should always have the second smallest value
  • else, return True, because we found a number that's greater that first and second, which means we found a triplet subsequence

In the above example, the point where you have reached 0 and subsequently updating first_num = 0 can make you confused as you might think that this no longer is a subsequence (since second_num = 2 comes before first_num = 0). Of course, since we have updated the first_num, if we want to return the actual subsequence, we might need to have another placeholder variable that will hold the previously recorded first_num before it is updated. However, for this problem, we are only looking for the existence of a valid increasing triplet subsequence, even though first_num and second_num are out of order, we don't need to worry about it.

To make this more illustrative, observe the following example.

nums = [1,2,0,3] # should return True

1. first_num = 1
2. second_num = 2
3. first_num = 0
4. return True

The increasing triplet subsequence is 1, 2, and 3. Even though first_num is updated in Line 3, second_num is never updated again. However, you can tell that there exists another number before second_num which is definitely BIGGER than the last updated first_num but SMALLER than second_num. This is a very important observation. Therefore, you can safely say that there exists an increasing triplet subsequence as soon as you see a number which is bigger than the last updated first_num and second_num even though that last updated first_num is not one of the actual numbers of the increasing triplet subsequence.