Problem Overview
LeetCode 334 — Increasing Triplet Subsequence asks you to return true if there exist indices i < j < k such that nums[i] < nums[j] < nums[k]. You do not need to find the indices; you only need to determine whether such a triplet exists anywhere in the array.
The brute-force approach of checking all triples runs in O(n³) time, which is too slow. The follow-up challenge is to solve it in O(n) time and O(1) extra space — no sorting, no hash sets, no auxiliary arrays.
The key insight is that you do not need to track the full longest increasing subsequence. You only care whether a subsequence of length 3 exists, which lets you compress the entire LIS algorithm down to just two scalar variables.
- Return true if indices i < j < k exist with nums[i] < nums[j] < nums[k]
- No need to return the actual indices — only a boolean answer
- Must be O(n) time and O(1) space per the follow-up constraint
- Brute force O(n³) triple loop is too slow for large inputs
- Sorting destroys order — cannot sort and then search
- Solution compresses the LIS problem to tracking only two values
Two-Variable Greedy
The greedy strategy uses two variables: first holds the smallest value seen so far, and second holds the smallest value seen that is strictly greater than some earlier first. Initially both are set to positive infinity.
For each number in the array: if it is less than or equal to first, update first to that number. Otherwise if it is less than or equal to second, update second to that number. Otherwise — the number is strictly greater than second — return true immediately because a valid triplet has been found.
The algorithm returns false after the loop if no element exceeded second. This single pass over the array, with only two variables and no extra data structures, achieves the required O(n) time and O(1) space bounds.
This Is LIS of Length 3 Compressed to Two Variables
This is the patience sorting / LIS algorithm compressed to two variables: first = tails[0] (smallest tail of any increasing subsequence of length 1), second = tails[1] (smallest tail of any increasing subsequence of length 2). Any value strictly greater than second means tails would grow to length 3 — a triplet exists. The full LIS algorithm uses an array of tails; here you only need the first two slots.
Algorithm
Initialize first and second to positive infinity (float("inf") in Python, Integer.MAX_VALUE in Java). These sentinels ensure that the first number processed will always update first, and the second distinct number will update second.
Iterate through each number in the array in order. Apply three conditions in sequence: if num is at most first, set first = num; else if num is at most second, set second = num; else return true. The order of these conditions matters — the first check must come before the second.
After the loop completes without returning true, return false. The loop condition is simply iterating every element once, giving a clean O(n) traversal with constant-time work per element.
- 1first = +infinity, second = +infinity
- 2For each num in nums:
- 3 — if num <= first: first = num
- 4 — elif num <= second: second = num
- 5 — else: return True (triplet found — num > second > first)
- 6Return False (no triplet found)
Why Updating First Does Not Break Second
The subtlest point in this algorithm is that first and second do not always belong to the same subsequence. When first is updated to a smaller value after second has already been set, the new first appears later in the array than the element that originally established second.
Despite this, second remains valid as a "second element" of some increasing subsequence. When second was set, it had a valid first before it at an earlier index. Even though first now points to a smaller number that appeared after second in the original array, the ghost of the original first still makes second legitimate.
The correctness guarantee is: if any element strictly exceeds second, there must exist a valid triplet. The element exceeding second is the third. Second itself was set because some element greater than first-at-that-time appeared. And first-at-that-time was some element before second. So all three ordering constraints i < j < k and nums[i] < nums[j] < nums[k] are satisfied.
First and Second Are Not Always from the Same Subsequence
This is the subtlest point: first and second do not always belong to the same subsequence at the same time. Second carries a "ghost" first — the value of first when second was originally set. Even if first later updates to a smaller number (appearing after second in the array), second is still a valid second element because its original first predecessor still exists at an earlier index. The invariant is: second was once greater than some earlier first, and that relationship is permanent.
Walk-Through Example
Trace [2, 1, 5, 0, 4, 6] through the algorithm. Start with first = inf, second = inf.
num=2: 2 <= inf so first=2. num=1: 1 <= 2 so first=1. num=5: 5 > 1 and 5 > inf? No, 5 <= inf so second=5. num=0: 0 <= 1 so first=0. Now first=0 but second=5 was set when first was 1 — second still valid. num=4: 4 > 0 and 4 <= 5 so second=4. num=6: 6 > 0 and 6 > 4 — return true!
The triplet is not (0, 4, 6) even though first=0. The actual triplet uses the ghost first=1 that was in place when second=5 was set, then refined to 4. The valid triplet is (1, 4, 6) or (2, 5, ...) — the algorithm detects existence without pinpointing which triplet.
- 1Start: first=inf, second=inf
- 2num=2: 2 <= inf → first=2
- 3num=1: 1 <= 2 → first=1
- 4num=5: 5 > 1, 5 <= inf → second=5
- 5num=0: 0 <= 1 → first=0 (second still = 5, ghost first = 1)
- 6num=4: 4 > 0, 4 <= 5 → second=4
- 7num=6: 6 > 0 and 6 > 4 → return True! Triplet exists.
Code Walkthrough: Python and Java
Python solution: def increasingTriplet(nums): first = second = float("inf"); for num in nums: if num <= first: first = num; elif num <= second: second = num; else: return True; return False. Three-branch if/elif/else inside a single for loop. float("inf") initializes both sentinels. O(n) time, O(1) space.
Java solution: public boolean increasingTriplet(int[] nums) { int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE; for (int num : nums) { if (num <= first) first = num; else if (num <= second) second = num; else return true; } return false; }. Integer.MAX_VALUE serves as positive infinity. Same three-branch logic, same complexity.
Both implementations are concise — under 10 lines — because the two-variable greedy reduces the problem to a single scan with constant work. The elegance of the solution comes from recognizing it as LIS of length 3 rather than a general subsequence problem.
Use <= Not < When Updating First and Second
Use <= (less than or equal) not < (strictly less than) when checking whether to update first and second. Equal values do not form an increasing triplet, so [1, 1, 1] must return false. If you use strict less-than for the update checks, first and second may not update correctly for arrays with repeated minimum values, leading to false positives. The condition num <= first means "this value is no larger than our current first — update it"; the else branch then catches strictly greater values.