Leetcode 334. Increasing Triplet Subsequence

January 3, 2020

334. Increasing Triplet Subsequence

The general idea is to keep track of a minimum and middle value. If a maximum appears we have a solution. The secrete, is to understand that we while keeping a minimum its index can, and should, change even for an index higher than the middle. The idea is that if a minimun is lower than the previous minimun the solution keeps holding, with either “minimun indexes” but by doing so we open the door for a new solution.

See example [20, 100, 10, 12, 5, 13] in this case the solution is 10, 12, 13 but the code actually sets the minimun as 5, 12, 13. Either way, there is a solution as 5 is lower then 10. If we dont update the minimun we would fail this scenario [20, 100, 10, 12, 5, 7, 8].


Runtime Beats 88.34% of users with Python3

Memory Beats 60.16% of users with Python3

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        first_num = None
        second_num = None
        for n in nums:
            if first_num is None or n <= first_num:
                first_num = n
            if second_num is None or n <= second_num:
                second_num = n
                return True
        return False