Leetcode 334. Increasing Triplet Subsequence (Python)

Related Topic

Dynamic-Programming.

Description

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Sample I/O

Example 1

Input: [1,2,3,4,5]
Output: true 

Example 2

Input: [5,4,3,2,1]
Output: false

Note:

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Methodology

This question can be solved by Dynamic Programming. It is similar with question 300. Longest Increasing Subsequence. The only difference is return true when the length of increasing subsequence reach to 3.

However, if we want to reach O(n) time and O(1) space. We need a different way.

For the classic dynamic programming way

Find the base case:

Init each element of dp list to 1 as there is at least 1 number of increasing subsequence unless the input is empty list.

Find the pattern:

If the current element is greater than prevous element, then current number of increasing subsequence is the previous number of increasing subsequence + 1.If the current element is greater than prevous element, then current number of increasing subsequence is the previous number of increasing subsequence + 1.

Above is the basic idea, however, you can optimazed it.

The classic dynamic programming method will compare each previous element with the current element to update the current number of increasing subsequence. However I found this is not efficent. Once the current element is greater than the max element of previous, there is no need to compare more previous elements.

Answer:

Return true when the length reach to 3

For the O(n) way without using dynamic programing

We init the smallest number and second smallest number. If there is a number that greater than second smallest number then we return true.

Answer:

Return true when there are number that greater than second smallest number

Code 1 (Inheriate code from question 334)

def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums)<3: return False
        size = len(nums)
        dp = [1]*size
        pre_max = nums[0]
        for i in range(1,size):
            pre_max = nums[i-1] if nums[i-1]>pre_max else pre_max
            for j in range(i-1,-1,-1):
                if nums[i]>nums[j]:
                    if nums[j]==pre_max:
                        dp[i]=max(dp[i],dp[j]+1)
                        break
                    dp[i]=max(dp[i],dp[j]+1)
        return True if max(dp)>=3 else False

BigO

Create dp list will cost O(n) and iterate the dp will cost ((n-1)^2) in total will be O((n-1)^2+n)

Code 2 (without dynamic programming)

def increasingTriplet(self, nums: List[int]) -> bool:
        first, second = float('inf'), float('inf')
        for num in nums:
            if num <= first:
                first = num
            elif num <= second:
                second = num
            else:
                return True
        return False

BigO

the total time consumption is O(n)