LeetCode 334. Increasing Triplet Subsequence

Description

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

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.

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

Example 1:

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

Example 2:

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

Explanation

Forward to create a list of the smallest number at each index position. Backward to create a list of the greatest number at each index position. If any number at same index greater than the number in forward, and smaller than the number in backward, then a triplet found.

Python Solution

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        forward = []
        backward = []
        
        forward.append(nums[0])
        
        for i in range(1, len(nums)):
            num = nums[i]
            if num < forward[i - 1]:
                forward.append(num)
            else:
                forward.append(forward[i - 1])
                
        backward.append(nums[len(nums) - 1])
        for i in range(1, len(nums)):
            num = nums[len(nums) - i - 1]            
            if num > backward[i - 1]:
                backward.append(num)
            else:
                backward.append(backward[i - 1])                

        backward.reverse()
        
        for i in range(0, len(nums)):
            num = nums[i]
            if backward[i] > num > forward[i]:
                return True      
            
        return False

• Time complexity: O(N).
• Space complexity: O(N).