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.

Increasing Triplet Subsequence - LeetCode Solution

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.

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

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. This approach avoids the overhead of full subsequence tracking and leverages the minimal state needed to detect the pattern.

Optimal Approach

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.

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.

Solution

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

1

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.

2

Iterate Through Array and Update Trackers Greedily

6for n in nums:
  if n <= first:
      first = n
  elif n <= second:
      second = n
  else:
      return True

Objective

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

Key Insight

The algorithm compares each number to the current smallest and second smallest. If the number is smaller or equal to the smallest, it updates the smallest. If it is larger than the smallest but smaller or equal to the second smallest, it updates the second smallest. If it is larger than both, it confirms the existence of an increasing triplet subsequence and returns true immediately. This greedy update ensures the minimal candidates are always tracked, enabling early detection without full subsequence reconstruction.

Interview Quick-Check

Core Logic

The greedy update rules ensure that the smallest and second smallest values represent the best candidates for the first two elements of an increasing triplet.

State & Boundaries

The loop terminates early upon finding a number larger than both trackers, guaranteeing O(n) time.

Common Pitfalls & Bugs

Failing to use '<=' in comparisons can cause incorrect updates and missed subsequences.

3

Return False if No Increasing Triplet Found

14	`return False`

Objective

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

Key Insight

If the loop completes without returning true, it means no element was found that is larger than both the smallest and second smallest tracked values, so no increasing triplet subsequence exists. Returning false correctly signals this outcome.

Interview Quick-Check

Core Logic

Returning false after the loop ensures the function only confirms existence when the triplet condition is met.

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.

Line 11 Critical

else:

Identify that the current number completes an increasing triplet.

Reaching this branch means the current number is greater than both 'first' and 'second', since the previous conditions failed. This confirms an increasing triplet subsequence has been discovered.

Line 3 Core

first = float('inf')

Initialize 'first' to positive infinity to represent the smallest candidate.

Setting 'first' to infinity ensures any number in the array will be smaller, allowing the algorithm to update it correctly as the smallest value seen so far.

Line 4 Core

second = float('inf')

Initialize 'second' to positive infinity to represent the second smallest candidate.

Similarly, 'second' starts at infinity so it can be updated to the smallest number greater than 'first', maintaining the minimal second element for the subsequence.

Line 14 Core

return False

Return false if no increasing triplet subsequence is found after full iteration.

If the loop completes without returning true, it means no valid triplet exists, so returning false correctly signals this outcome.

Line 7 Core

if n <= first:

Check if the current number is less than or equal to 'first'.

If true, this number becomes the new smallest candidate, ensuring 'first' always holds the minimal value encountered so far.

Line 9 Core

elif n <= second:

Check if the current number is less than or equal to 'second'.

If the number is larger than 'first' but smaller or equal to 'second', it becomes the new candidate for the second element in the subsequence, maintaining the minimal second value.

Line 6 Standard

for n in nums:

Begin iterating through each number in the input array.

A single pass through the array is sufficient to detect the increasing triplet subsequence by updating the two trackers greedily.

Test Your Understanding

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

Because any increasing triplet must have a first and second element smaller than the third, maintaining the smallest and second smallest candidates allows immediate detection when a third larger element appears, confirming the subsequence without tracking all elements.

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`

6	`for n in nums:`
7	`if n <= first:`
8	`first = n`
9	`elif n <= second:`
10	`second = n`
11	`else:`
12	`return True`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize First and Second Minimum Trackers

Iterate Through Array and Update Trackers Greedily

Return False if No Increasing Triplet Found

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.