334.Increasing_Triplet_Subsequence(Medium).md

334. Increasing Triplet Subsequence (Medium)

Date and Time: Sep 29, 2024, 21:06 (EST)

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

Question:

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 1:

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

Output: true

Explanation: Any triplet where i < j < k is valid.

Example 2:

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

Output: false

Explanation: No triplet exists.

Example 3:

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

Output: true

Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Constraints:

• 1 <= nums.length <= 5 * 10^5

• -2^31 <= nums[i] <= 2^31 - 1

Walk-through:

Initialize i, j = float("inf), then for num in nums, if we find smaller value for i or j, we update i or j, if num is greater than i and j, we can return True. Otherwise, we return False.

Python Solution:

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        # if num < i or j, update i or j
        # else, num > i and num > j, return True
        i = j = float("inf")
        for num in nums:
            if num <= i:
                i = num
            elif num <= j:
                j = num
            else:
                return True
        return False

Time Complexity: $O(n)$
Space Complexity: $O(1)$