leetcode

Increasing Triplet Subsequence

Increasing Triplet Subsequence

Binary Search Version - 40ms O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        first = second = float('inf')
        for x in nums:
            if x <= first:
                first = x
            elif x <= second:
                second = x
            else:
                return True
        return False

test code

1
2
3
4
5
In [306]: s = Solution(); t = s.increasingTriplet(n); print(t)
True
In [307]: n
Out[307]: [1, 3, 6, 7, 9, 4, 10, 5, 6]

leet code