#334

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Increasing Triplet Subsequence

Identify if an array contains a strictly increasing triplet by maintaining a running minimal and middle value efficiently.

array greedy

Problem Statement

Given an integer array nums, determine whether there exists three indices i, j, k with i < j < k such that nums[i] < nums[j] < nums[k]. Return true if such a triplet exists, otherwise return false.

You must solve this using a method that efficiently tracks potential minimum and middle values without explicitly generating all subsequences. Example inputs include nums = [1,2,3,4,5] which returns true, and nums = [5,4,3,2,1] which returns false.

Examples

Example 1

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

Output: true

Any triplet where i < j < k is valid.

Example 2

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

Output: false

No triplet exists.

Example 3

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

Output: true

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

Constraints

1 <= nums.length <= 5 * 105
-231 <= nums[i] <= 231 - 1

Solution Approach

Greedy Tracking of Minimum and Middle

Initialize two variables first and second to track the smallest and second smallest numbers. Iterate through the array: if the current number is less than first, update first; else if it's less than second, update second; else a number greater than second indicates an increasing triplet exists.

Invariant Validation

Ensure that first <= second always holds during iteration. Each update preserves the invariant that first is the minimal value seen so far and second is the smallest number greater than first, guaranteeing the greedy choice is valid for subsequence detection.

Early Exit Optimization

As soon as a number larger than second is encountered, return true immediately. This avoids unnecessary iteration over remaining elements, making the algorithm efficient for large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because the array is traversed once. Space complexity is O(1) as only two variables are maintained regardless of input size.

What Interviewers Usually Probe

Are you maintaining only essential state variables instead of generating all subsequences?
Can you justify why tracking first and second numbers guarantees correctness?
How would your solution behave on strictly decreasing arrays or repeated elements?

Common Pitfalls or Variants

Common pitfalls

Attempting to store all subsequences, leading to O(n^3) time complexity.
Failing to update the second variable correctly when encountering smaller numbers than second but larger than first.
Returning false too early without fully validating all candidates in one pass.

Follow-up variants

Increasing Quadruplet Subsequence: extend tracking to three variables to detect four-element increasing sequences.
Longest Increasing Subsequence Length ≥ k: generalize invariant tracking to maintain k-1 variables for arbitrary length sequences.
Strictly Decreasing Triplet: apply similar logic but track maximal decreasing values instead of minimal increasing ones.

FAQ

What is the key pattern behind the Increasing Triplet Subsequence problem?

The pattern is greedy choice plus invariant validation, maintaining minimal and middle values to detect a valid triplet.

Can this approach handle arrays with repeated numbers?

Yes, the solution correctly updates first and second, ensuring strictly increasing conditions even with duplicates.

What is the time complexity for this method?

It is O(n) because each element is processed once and only two variables are maintained.

How do I know when to return true early?

Return true immediately when a number larger than the current second variable is found, indicating a valid triplet exists.

Is additional space required for storing subsequences?

No, only two variables are tracked, so the space complexity is O(1) regardless of input size.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

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

Continue Practicing

#330 patching array #324 wiggle sort ii #321 create maximum number