Increasing Triplet Subsequence — LeetCode 334 Python Solution

The problem

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example

Input

nums = [1,2,3,4,5]

Output

true

Explanation

Any triplet where i < j < k is valid.

Python solution

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        mi, mid = inf, inf
        for num in nums:
            if num > mid:
                return True
            if num <= mi:
                mi = num
            else:
                mid = num
        return False

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 334. Increasing Triplet Subsequence is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems