Things

Increasing Triplet Subsequence (LC 334)

5 min read

Pattern: Greedy, keep the two smallest “ends” → a 3-length LIS
Difficulty: Medium
Time: O(n) | Space: O(1)

Problem

Given nums, return true if there are indexes i < j < k with nums[i] < nums[j] < nums[k]. Otherwise false.
Follow-up: O(n) time and O(1) space.

nums = [1,2,3,4,5] → true
nums = [5,4,3,2,1] → false
nums = [2,1,5,0,4,6] → true (0,4,6 or 1,5,6)

A subsequence, not a subarray. The three values don’t have to be next to each other, only in order.

Core idea

Keep the smallest possible first value and the smallest possible second value seen so far. Anything bigger than both closes the triplet.

Two slots:

  • first: the smallest number seen so far.
  • second: the smallest number that has something smaller before it.

For each x:

  • x <= first → better start, overwrite first.
  • x <= second → better middle, overwrite second.
  • otherwise x > second → done.

Keeping both as small as possible is the greedy part. A smaller second can only make it easier for a later number to beat it.

Brute force first

Three nested loops. O(n³), and n goes up to 5 × 10⁵, so it times out. Useful as a checker though.

function brute(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++)
    for (let j = i + 1; j < nums.length; j++)
      for (let k = j + 1; k < nums.length; k++)
        if (nums[i] < nums[j] && nums[j] < nums[k]) return true;
  return false;
}

O(n) space: prefix min + suffix max

Fix the middle j. It works as a middle if something smaller exists on its left and something bigger on its right. So you only need the min to the left and the max to the right of every index. Same left/right split as Product of Array Except Self (LC 238).

function increasingTriplet(nums: number[]): boolean {
  const n = nums.length;
  if (n < 3) return false;
  const leftMin = new Array(n), rightMax = new Array(n);
  leftMin[0] = nums[0];
  for (let i = 1; i < n; i++) leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
  rightMax[n - 1] = nums[n - 1];
  for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
 
  for (let j = 1; j < n - 1; j++) {
    if (leftMin[j - 1] < nums[j] && nums[j] < rightMax[j + 1]) return true;
  }
  return false;
}

Easy to argue correct. O(n) time, O(n) space. The follow-up asks you to drop the arrays.

Best: two variables

function increasingTriplet(nums: number[]): boolean {
  let first = Infinity, second = Infinity;
  for (const x of nums) {
    if (x <= first) first = x;        // new smallest
    else if (x <= second) second = x; // bigger than first, new best middle
    else return true;                 // bigger than both
  }
  return false;
}

Trace for [2,1,5,0,4,6]:

xfirstsecondnote
22∞
11∞smaller start
515pair 1,5
005first moves past second
404pair 0,4
6046 > 4 → true

Why it’s still correct when first jumps ahead

This is the part that trips people. At x = 0 above, first = 0 sits at index 3, after second = 5 at index 2. The variables no longer describe a real pair.

That’s fine, because second carries a promise: when it was set, some value smaller than it already existed before it. Moving first later doesn’t erase that earlier value. So when x > second shows up, the real triplet is (old first, second, x), here 1, 5, x.

first only matters for the next update to second. A smaller first lets a smaller middle in later, which is exactly what happens at x = 4.

Another trace, [20,100,10,12,5,13]:

xfirstsecond
2020∞
10020100
1010100
121012
5512
13512 → true (10, 12, 13)

The answer’s real triplet is 10, 12, 13, but the variables say 5, 12. The function returns a yes/no, so it never needs the actual indexes.

Why <= and not <

The triplet must be strictly increasing. With <, an equal value falls through to the else branch:

[1,1,1]  with <   →  true   (wrong)
[1,1,1]  with <=  →  false

With <, the second 1 isn’t < first but is < ∞, so it becomes second. The third 1 is neither < first nor < second, so it returns true. <= makes duplicates overwrite the slot instead of climbing.

This is LIS with patience sorting, capped at length 3. In the O(n log n) LIS, tails[k] holds the smallest possible tail of an increasing subsequence of length k + 1. Here first = tails[0], second = tails[1], and hitting tails[2] means the answer is true. With only two slots, the binary search becomes two comparisons.

It generalises: “is there an increasing subsequence of length k?” → keep k - 1 slots, O(n·k) or O(n log k).

Gotchas

  • <=, not <. Duplicates otherwise fake a triplet.
  • first and second aren’t a real pair after first moves. Don’t try to return indexes from them.
  • Infinity as the start value, not nums[0] or 0. 0 breaks on negative inputs.
  • Subsequence, not subarray. A sliding window of size 3 is the wrong problem.
  • Order of the ifs matters. Check first before second, or a new minimum lands in the middle slot.

Pattern to remember

“Does an increasing run of length k exist?” → greedily keep the smallest tail for each length. A smaller tail never hurts.

Practice

  1. Return the actual indexes (i, j, k). You’ll need to remember the first that was current when second was set.
  2. Generalise to length k with a tails array and binary search.
  3. Decreasing version: does nums[i] > nums[j] > nums[k] exist?
  4. 132 Pattern (LC 456): same three-index shape, but the middle is the largest. Needs a monotonic stack instead.

Graph View