10/26/2020

[LeetCode] 334. Increasing Triplet Subsequence

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

Use 2 caches to save the minimal number from left and the maximal number from right of each position.

Return true when minimal_from_left < nums[i] < maximal_from_right.

Time Complexity = O ( N )

Space Complexity = O ( 2 * N )


class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        mi = [0] * len(nums)
        mx = [0] * len(nums)
        
        mi_so_far = nums[0]
        for i in range(len(nums)):
            mi_so_far = min(mi_so_far, nums[i])
            mi[i] = mi_so_far
        
        mx_so_far = nums[-1]
        for i in reversed(range(len(nums))):
            mx_so_far = max(mx_so_far, nums[i])
            mx[i] = mx_so_far
        
        for i in range(len(nums)):
            if mi[i] < nums[i] < mx[i]:
                return True
        
        return False

Space Complexity O(1) Solution:

Use 2 pointers m1, m2 to save number with smaller value.

It finds the increasing triplet when find a number larger than both m1 and m2.

 
class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        m1 = m2 = 2 ** 31 - 1 #MAX_INT
        
        for n in nums:
            if m1 >= n : 
                m1 = n
            elif m2 >= n :
                # find m2 > m1
                m2 = n
            else:
                # find m3 > m2 > m1
                return True
        
        return False

No comments:

Post a Comment