LC 334

Solution to LeetCode 334 Increasing Triplet Subsequence.

LeetCode 334

Increasing Triplet Subsequence (Medium). [link]

1] Bi-directional iteration. MIN stores the smaller values for each value in nums and MAX stores the larger values for each value in nums. We iterate through the nums to find if there is a value satisfying MIN[i-1] < nums[i] < MAX[i+1]. Time complexity O(n), space complexity O(n).

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if n < 3:
            return False
          
        MIN = [0] * n
        MIN[0] = nums[0]
        for i in range(1, n):
            MIN[i] = min(MIN[i-1], nums[i])
            
        MAX = [0] * n
        MAX[n - 1] = nums[-1]
        for j in range(n-2, -1, -1):
            print(j)
            MAX[j] = max(MAX[j+1], nums[j])
            
        for k in range(1, n-1):
            if MIN[k-1] < nums[k] < MAX[k+1]:
                return True
        return False
            

2] Greedy. To find a triplet subsequence (first, second, num), we want first and second to be as small as possible. Time complexity O(n), space complexity O(1).

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        n = len(nums)
        if n < 3:
            return False
        first, second = nums[0], float('inf')
        for i in range(1, n):
            num = nums[i]
            if num > second:
                return True
            if num > first:
                second = num
            else:
                first = num
        return False