We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Increasing Triplet Subsequence

Number: 334

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Meta, Microsoft, TikTok, Yahoo, Uber, IBM, Nutanix

Problem Description

Given an integer array nums, determine whether there exists a triplet of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. Return true if such a triple exists; otherwise, return false.

Key Insights

  • You are asked to find three numbers in increasing order.
  • The goal is to achieve this in O(n) time and O(1) space.
  • Maintaining two variables for the smallest and second smallest numbers found so far allows checking if a greater third number exists.
  • Each element is compared to update these candidates based on a greedy approach.

Space and Time Complexity

Time Complexity: O(n) — traverse the list once
Space Complexity: O(1) — only constant extra space is used

Solution

The algorithm scans through the array while keeping two variables: "first" representing the smallest value encountered so far and "second" for the next smallest value greater than "first". For each number:

  • If it is less than or equal to "first", update "first".
  • Else if it is less than or equal to "second", update "second".
  • Otherwise, a valid triplet is found and the function returns true. This efficient approach uses the greedy method to maintain candidates for the first two numbers and automatically finds a valid third number if it exists.

Code Solutions

def increasingTriplet(nums):
    # Initialize first and second to be infinity
    first = float('inf')
    second = float('inf')
    
    # Loop through each number in the list
    for num in nums:
        # Update first if current num is smaller than or equal first
        if num <= first:
            first = num
        # Update second if current num is smaller than or equal second but greater than first
        elif num <= second:
            second = num
        # If current num is greater than both first and second, a valid triplet is found
        else:
            return True
    return False

# Sample Test
print(increasingTriplet([2,1,5,0,4,6]))  # Expected output: True
← Back to All Questions