https://leetcode.com/problems/increasing-triplet-subsequence

This problem is special case of problem 300 Longest Increasing Subsequence, but here we are asked if this length is more or equal to 3. Let us use the same logic here: we keep two-elements array a, where:

  1. a[0] is the smallest end among all increasing subsequences of length 1.
  2. a[1] is smallest end among all increasing subsequences of length 2. Note, that a[1] >= a[0] always.

We iterate over nums and check conditions: if elem < a[0], we can create 1 elements increasing subsecuense with smaller end. If a[0] < elem < a[1], we can update increasing subsequence of size 2. In other case we found subsequnce of length 3 and we can return True.

Complexity: time complexity is O(n): we iterate over our data once. Space complexity is O(1).

Remark: see my solution of problem 0300 Longest Increasing Subsequence: https://leetcode.com/problems/longest-increasing-subsequence/discuss/667975/Python-3-Lines-dp-with-binary-search-explained

class Solution:
    def increasingTriplet(self, nums):
        a = [float("inf")]*2
        for elem in nums:
            if elem < a[0] : a[0] = elem
            if elem < a[1] and elem > a[0]: a[1] = elem
            if elem > a[1] : return True
        return False

If you like the solution, you can upvote it on leetcode discussion section: Problem 0334