334. Increasing Triplet Subsequence

Problem Statement

link: LeetCode.cn LeetCode

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

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

Input: nums = [2,1,5,0,4,6] Output: true

Solution Approach

The solution employs a greedy approach to find an increasing triplet subsequence in the given array nums.

Algorithm

1. Initialization: Initialize two variables first and second to positive infinity.

2. Finding Triplet: Iterate through each element n in the array.

-If n is less than or equal to first, update first to n. -Otherwise, if n is less than or equal to second, update second to n. -If none of the above conditions are met, return True as an increasing triplet subsequence (i.e., first, second, and n) has been found.

1. No Triplet Found: If the loop completes without finding an increasing triplet subsequence, return False.

Implement

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

    
       

    
    

Twitter  facebook  Email