334. Increasing Triplet Subsequence

Solution:

  • this was hard even though the solution looks extremely simple.
  • The below discussion post helped a lot. link

The problem “Increasing Triplet Subsequence” is to find out if there exists a subsequence of a given array such that the elements in the subsequence form an increasing triplet.

One brute force approach to solve this problem is to generate all possible subsequences of the array, and then check if any of them forms an increasing triplet. This approach has a time complexity of O(2^N), where N is the size of the array. This approach is not efficient as the complexity grow exponentially as the size of the array increases.

A better approach would be to use a two-pointer technique to keep track of the smallest and second smallest elements seen so far in the array, and then iterate through the array. If we find an element that is greater than the second smallest element, then we have found an increasing triplet subsequence. This approach has a time complexity of O(N) and space complexity of O(1).

    def increasingTriplet(self, nums: List[int]) -> bool:
        smallest = s_smallest = float('inf')

        i = 0
        while i < len(nums):
            if nums[i] <= smallest:
                smallest = nums[i]
            else:
                if nums[i] <= s_smallest:
                    s_smallest = nums[i]
                else:
                    return True
            i += 1

        return False
Tags