334.Increasing Triplet Subsequence

Tags: [trick]

Link: https://leetcode.com/problems/increasing-triplet-subsequence/\#/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.

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

Examples:
Given[1, 2, 3, 4, 5],
returntrue.

Given[5, 4, 3, 2, 1],
returnfalse.

Solution: trick

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if not nums or len(nums) < 3:
            return False

        first_small = sys.maxint
        second_small = sys.maxint
        for n in nums:
            if n <= first_small:
                first_small = n
            elif n <= second_small:
                # current n > first_small
                second_small = n
            else:
                # current n > second_small > first_small.
                return True

        return False

Revelation:

• We try to find a moment, which can satisfy the current num > second__small > first__small at the same time.

Note:

• Time complexity = O(n), n is the number of elements in the given array.
• Space complexity = O(1).