How do you solve Increasing Triplet Subsequence?

Initialize two variables, first and second, to infinity. Iterate through nums. For each number n, if n is less than or equal to first, update first to n. Else if n is less than or equal to second, update second to n. Otherwise, n is greater than both first and second, so return true immediately. If the loop ends without returning, return false. This guarantees O(n) time and O(1) space.

Increasing Triplet Subsequence

Q: What is the time complexity of Increasing Triplet Subsequence?

O(n). The algorithm performs a single pass through the array, updating two variables and performing constant-time comparisons per element.

Q: What pattern does Increasing Triplet Subsequence use?

The Pattern: Greedy Algorithms (State Compression for Subsequence Detection) The Heuristic: When searching for a fixed-length increasing subsequence, track the minimal candidates for each subsequence position greedily; updating these candidates ensures that the discovery of a larger element confirms the subsequence without full enumeration.

Medium Greedy Algorithms

Problem

Given an integer array nums, return true if there exists a strictly increasing subsequence of length 3, and false otherwise.

1 ≤ nums.length ≤ 5 * 10⁵
−2³¹ ≤ nums[i] ≤ 2³¹ - 1

Example

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

Output: true

The algorithm maintains two variables representing the smallest and second smallest values found so far in an increasing order. Iterating through nums, it updates these variables greedily: first to 2, then updates to 1 since 1 < 2, then second to 5 since 5 > 1, then first to 0 since 0 < 1, then second to 4 since 4 > 0, and finally encounters 6 which is greater than second (4), confirming the existence of an increasing triplet subsequence (0, 4, 6). The function returns true immediately upon this discovery.

Approach

Straightforward Solution

A brute-force approach would check all triplets with three nested loops, resulting in O(n^3) time, which is infeasible for large inputs. A more efficient O(n^2) approach uses dynamic programming to track the length of the longest increasing subsequence ending at each index, but this is still too slow for large arrays.

Core Observation

To detect an increasing triplet subsequence, it suffices to track two increasing values in order. If a third value larger than both is found, the subsequence exists. This relies on the principle that any increasing subsequence of length 3 must have a first and second element smaller than the third.

Path to Optimal

Preview

The key insight is that only the smallest and second smallest values matter to detect a triplet. By greedily updating these two values while scanning the array once, the algorithm can confirm the existence of a triplet in O(n) time and O(1) space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize two variables, first and second, to infinity. Iterate through nums…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm performs a single pass through the array, updating two variables and performing constant-time comparisons per element.

Space

O(1)

Only two variables are maintained regardless of input size, resulting in constant auxiliary space.

Pattern Spotlight

Greedy Algorithms (State Compression for Subsequence Detection)

When searching for a fixed-length increasing subsequence, track the minimal candidates for each subsequence position greedily; updating these candidates ensures that the discovery of a larger element confirms the subsequence without full enumeration.

Solution

Python

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

Step-by-Step Solution

Initialize First and Second Minimum Trackers

3first = float('inf')
4second = float('inf')

Objective

To set up two variables representing the smallest and second smallest values found so far in the array.

Key Insight

Initializing both variables to infinity ensures that any number in the array will update them appropriately. This setup creates a baseline for comparison that allows the algorithm to greedily track the minimal increasing pairs needed to detect a triplet subsequence.

Interview Quick-Check

Core Logic

Using two variables to track the smallest and second smallest values compresses the subsequence detection state into constant space.

Common Pitfalls & Bugs

Initializing these variables incorrectly (e.g., to zero or the first element) can cause missed subsequences or incorrect results.

Iterate Through Array and Update Trackers Greedily

To scan the array once, updating the smallest and second smallest values or returning true when a valid triplet is found.

Return False if No Increasing Triplet Found

To return false after completing the iteration if no increasing triplet subsequence exists.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 12 Critical

return True

Return True to signal that an increasing triplet subsequence has been found.

Once an increasing triplet is detected, the algorithm immediately terminates because the problem only asks whether such a subsequence exists.

Line 8 Critical

first = n

Update 'first' to the current number.

This update is critical because it compresses the subsequence state to the minimal first element, enabling the greedy detection of the triplet without storing the entire subsequence.

Line 10 Critical

second = n

Update 'second' to the current number.

This line is essential because it refines the second candidate, allowing the algorithm to track the minimal increasing pair and detect when a third larger element appears.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why does tracking only two variables suffice to detect an increasing triplet subsequence?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Increasing Triplet Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Increasing Triplet Subsequence drill

or drill a free problem

1	`class Solution:`
2	`def increasingTriplet(self, nums: List[int]) -> bool:`
3	`first = float('inf')`
4	`second = float('inf')`
5
6	`for n in nums:`
7	`if n <= first:`
8	`first = n`
9	`elif n <= second:`
10	`second = n`
11	`else:`
12	`return True`
13
14	`return False`