248. Increasing Triplet Subsequence
🔗 LeetCode Problem: 334. Increasing Triplet Subsequence
📊 Difficulty: Medium
🏷️ Topics: Array, Greedy, DP - LIS
Problem Statement
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
Example 1:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.
Example 2:
Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.
Example 3:
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
Constraints:
- 1 <= nums.length <= 5 * 10^5
- -2^31 <= nums[i] <= 2^31 - 1
Follow up: Could you implement a solution that runs in O(n) time complexity and O(1) space complexity?
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "increasing triplet subsequence" for a moment. Let me understand:
Given: nums = [1,2,3,4,5]
Question: Can we find THREE numbers where each is bigger than previous?
Let me try:
Pick i=0 (value 1)
Pick j=1 (value 2) → 2 > 1 ✓
Pick k=2 (value 3) → 3 > 2 ✓
Found: 1 < 2 < 3 ✓
Answer: true ✓
Another example: nums = [5,4,3,2,1]
Can I find three increasing numbers?
5 is first... need something > 5, but all are smaller! ✗
4 is next... need something > 4, but all are smaller! ✗
Answer: false ✗
KEY INSIGHT: Find ANY three numbers in increasing order! 🔑
Not necessarily consecutive!
Just need i < j < k (indices)
And nums[i] < nums[j] < nums[k] (values)
Connection To Problem 247 (LIS)
Wait! This sounds like LIS (Longest Increasing Subsequence)!
PROBLEM 247: LIS
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: Find LENGTH of longest increasing subsequence
Answer: Integer (length)
Constraint: Any length
Example: [10,9,2,5,3,7,101,18]
LIS = [2,3,7,101] → length 4 ✓
PROBLEM 248: Increasing Triplet
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: Does there exist increasing subsequence of length 3?
Answer: Boolean (true/false)
Constraint: Specifically length 3!
Example: [1,2,3,4,5]
Exists triplet [1,2,3] → true ✓
KEY INSIGHT:
Problem 248 is a SPECIAL CASE of Problem 247!
We only need to check if LIS length >= 3! 🔑
Can we use LIS solution?
Yes! But it's O(n²) or O(n log n)
Can we do better for this special case? 🤔
Why This Special Case Allows Optimization
General LIS (any length k):
Need to track ALL possible subsequence lengths
O(n²) with DP or O(n log n) with binary search
Specific length (exactly 3):
Only need to track TWO values!
- Smallest value seen so far (potential first element)
- Smallest second value after first (potential second element)
- If we find third value > second, done! ✓
This allows O(n) time and O(1) space! 🚀
Think about it:
For triplet [a, b, c] where a < b < c:
We need to find:
1. Some value a (smallest possible)
2. Some value b > a (smallest possible after a)
3. Some value c > b (any value works!)
Only need TWO variables, not an array! ✓
🤔 Building Intuition - The Two-Variable Pattern
Understanding The Greedy Strategy
Key insight: We want to find three increasing numbers.
Strategy: Keep track of two "candidates":
first = smallest number seen so far
second = smallest number > first seen so far
As we scan the array:
If current > second:
Found triplet! ✓
(first < second < current)
Else if current > first:
Update second = current
(Found better second value)
Else:
Update first = current
(Found better first value)
Let me trace this for: nums = [2,1,5,0,4,6]
Start: first = ∞, second = ∞
i=0, num=2:
2 > second(∞)? NO
2 > first(∞)? NO
Update first = 2
State: first=2, second=∞
i=1, num=1:
1 > second(∞)? NO
1 > first(2)? NO
Update first = 1 ← Better first!
State: first=1, second=∞
i=2, num=5:
5 > second(∞)? NO
5 > first(1)? YES ✓
Update second = 5
State: first=1, second=5
i=3, num=0:
0 > second(5)? NO
0 > first(1)? NO
Update first = 0 ← Better first!
State: first=0, second=5
Note: first changed but second still valid!
We had [1, 5, ?] and now have [0, 5, ?]
But the [1, 5] pair still exists in history! 🔑
i=4, num=4:
4 > second(5)? NO
4 > first(0)? YES ✓
Update second = 4 ← Better second!
State: first=0, second=4
i=5, num=6:
6 > second(4)? YES! ✓✓✓
Found triplet!
Return true ✓
The triplet: [0, 4, 6] at indices (3, 4, 5) ✓
Why This Works - The Crucial Insight
QUESTION: When first changes, doesn't it break the subsequence?
Example from above:
We had first=1, second=5
Then first changed to 0
Doesn't this mean we need second > 0?
But second=5 was based on first=1! 🤔
ANSWER: It doesn't matter! Here's why:
When we update first to a smaller value:
- The OLD (first, second) pair STILL EXISTS in the array!
- We're just looking for a BETTER configuration
- If we find third > second, we win with OLD pair!
- If we find new second > new first, we have BETTER pair!
Visual proof:
Array: [... 1 ... 5 ... 0 ...]
^old ^old ^new
first second first
When we see 0:
Update first = 0
Keep second = 5
Case 1: Next element > 5
Use OLD triplet: [1, 5, next] ✓
Case 2: Next element between 0 and 5
Update second, now have [0, next, ?]
Better starting point!
Case 3: Next element > 5
Still use [1, 5, next] ✓
We can NEVER lose a valid triplet!
We only find BETTER configurations! 🔑
This is the BEAUTY of the greedy approach! ✓
Why Greedy Is Correct - Formal Proof
CLAIM: If triplet exists, this algorithm finds it.
PROOF by contradiction:
Assume: Triplet [a, b, c] exists at indices i < j < k
Algorithm returns false (claims no triplet)
Since algorithm returns false:
At position k, we had: num[k] <= second
But we know: c > b (from triplet definition)
When did we process b (at position j)?
Case 1: b > second at that time
→ Algorithm would have returned true
→ Contradiction! ✗
Case 2: b <= second at that time
→ We updated second = b
→ Now second = b
→ Later at k: c > b = second
→ Algorithm returns true
→ Contradiction! ✗
Case 3: b <= first at that time
→ We updated first = b
→ But we had a > something before b
→ That something < b < c
→ At position k: c > second
→ Algorithm returns true
→ Contradiction! ✗
All cases lead to contradiction!
Therefore: Algorithm is correct! QED ✓
Beautiful mathematics! ✓
🔴 Approach 1: Brute Force - Try All Triplets
The Straightforward Solution
Simplest idea: Try ALL possible triplets!
For each i:
For each j > i:
For each k > j:
If nums[i] < nums[j] < nums[k]:
Return true!
Return false (no triplet found)
This checks EVERY combination! ✓
Implementation
class Solution {
public boolean increasingTriplet(int[] nums) {
int n = nums.length;
// Try all possible triplets
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] < nums[j] && nums[j] < nums[k]) {
return true;
}
}
}
}
return false;
}
}
Why This Is Too Slow
TIME COMPLEXITY:
Three nested loops!
Outer: n-2 iterations
Middle: up to n-1 iterations
Inner: up to n iterations
Total: O(n³) ❌
For n = 500,000 (max constraint):
500,000³ = 125 × 10^15 operations
This would take YEARS! ❌
SPACE COMPLEXITY: O(1) ✓
Verdict: Correct but way too slow! ❌
🟡 Approach 2: Use LIS Solution
Applying What We Know
From Problem 247, we know how to find LIS!
If LIS length >= 3:
Return true ✓
Else:
Return false ✗
We can use either:
- O(n²) DP solution
- O(n log n) binary search solution
Let's use the O(n log n) one!
Implementation
class Solution {
public boolean increasingTriplet(int[] nums) {
// Use LIS binary search approach
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
tails.add(num);
} else {
tails.set(pos, num);
}
// Early termination: if we have 3 elements, triplet exists!
if (tails.size() >= 3) {
return true;
}
}
return false;
}
private int binarySearch(List<Integer> tails, int num) {
int left = 0;
int right = tails.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < num) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
Analysis
TIME COMPLEXITY:
For each element: O(log n) binary search
Total: O(n log n) ✓
For n = 500,000:
500,000 × log(500,000) ≈ 9.5 million operations
This works! ✓
SPACE COMPLEXITY:
Tails array: at most 3 elements (we return when size >= 3)
Total: O(1) ✓ (constant, not dependent on n)
Verdict: This works! But can we do better? 🤔
🟢 Approach 3: Two Variables (Optimal O(n) Solution)
The Brilliant Insight
Since we only need length 3:
We only need to track TWO values!
first = smallest value seen so far
second = smallest value > first seen so far
If we find any value > second → Found triplet! ✓
This requires only ONE PASS through the array!
O(n) time, O(1) space! 🚀
The Algorithm Step By Step
Initialize:
first = Integer.MAX_VALUE
second = Integer.MAX_VALUE
For each num in nums:
If num <= first:
first = num
(Found better/equal first candidate)
Else if num <= second:
second = num
(Found better/equal second candidate)
(Note: num > first guaranteed here!)
Else:
return true
(Found third element > second!)
(Triplet exists: first < second < num)
Return false
(No triplet found)
Simple and elegant! ✓
Detailed Example Walkthrough
Example 1: nums = [1,2,3,4,5]
Initialize: first = ∞, second = ∞
i=0, num=1:
1 <= ∞? YES
first = 1
State: first=1, second=∞
i=1, num=2:
2 <= first(1)? NO
2 <= second(∞)? YES
second = 2
State: first=1, second=2
Note: We have pair [1, 2] ✓
i=2, num=3:
3 <= first(1)? NO
3 <= second(2)? NO
Found triplet! [1, 2, 3] ✓
Return true ✓
Example 2: nums = [5,4,3,2,1]
Initialize: first = ∞, second = ∞
i=0, num=5:
5 <= ∞? YES
first = 5
State: first=5, second=∞
i=1, num=4:
4 <= first(5)? YES
first = 4 ← Better first!
State: first=4, second=∞
i=2, num=3:
3 <= first(4)? YES
first = 3 ← Better first!
State: first=3, second=∞
i=3, num=2:
2 <= first(3)? YES
first = 2 ← Better first!
State: first=2, second=∞
i=4, num=1:
1 <= first(2)? YES
first = 1 ← Better first!
State: first=1, second=∞
End of array, no triplet found!
Return false ✗
Example 3: nums = [2,1,5,0,4,6]
Initialize: first = ∞, second = ∞
i=0, num=2:
2 <= ∞? YES
first = 2
State: first=2, second=∞
i=1, num=1:
1 <= first(2)? YES
first = 1 ← Better first!
State: first=1, second=∞
i=2, num=5:
5 <= first(1)? NO
5 <= second(∞)? YES
second = 5
State: first=1, second=5
Note: We have pair [1, 5] ✓
i=3, num=0:
0 <= first(1)? YES
first = 0 ← Better first!
State: first=0, second=5
CRITICAL: Pair [1, 5] still exists in array!
We're just tracking better candidates! 🔑
i=4, num=4:
4 <= first(0)? NO
4 <= second(5)? YES
second = 4 ← Better second!
State: first=0, second=4
Note: We have pair [0, 4] ✓
i=5, num=6:
6 <= first(0)? NO
6 <= second(4)? NO
Found triplet! ✓
Which triplet?
We can use [0, 4, 6] at indices (3, 4, 5) ✓
OR we can use [1, 5, 6] at indices (1, 2, 5) ✓
Both valid! ✓
Return true ✓
Beautiful! ✓
Complete Implementation
class Solution {
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= first) {
// Found new smallest value
first = num;
} else if (num <= second) {
// Found new second value (guaranteed > first)
second = num;
} else {
// Found third value > second
// Triplet exists!
return true;
}
}
return false;
}
}
🔍 Detailed Edge Cases
Edge Case 1: Duplicate Values
nums = [1, 1, 1, 1, 1]
Trace:
i=0, num=1: first = 1
i=1, num=1: 1 <= first(1)? YES → first = 1
i=2, num=1: 1 <= first(1)? YES → first = 1
...
Result: false ✓
Why? We need STRICTLY increasing (< not <=)
Duplicates don't create increasing triplet! ✓
Edge Case 2: Decreasing Then Increasing
nums = [5, 4, 3, 2, 1, 2, 3]
Trace:
i=0, num=5: first = 5
i=1, num=4: first = 4
i=2, num=3: first = 3
i=3, num=2: first = 2
i=4, num=1: first = 1
i=5, num=2: 2 > first(1)? YES → second = 2
i=6, num=3: 3 > second(2)? YES → Found! ✓
Result: true ✓
Triplet: [1, 2, 3] at indices (4, 5, 6) ✓
Edge Case 3: First Changes After Second Set
nums = [2, 5, 3, 4, 5]
Trace:
i=0, num=2: first = 2
i=1, num=5: second = 5 (pair: [2, 5])
i=2, num=3: 3 > first(2)? YES, 3 <= second(5)? YES
→ second = 3 (better pair: [2, 3])
i=3, num=4: 4 > second(3)? YES → Found! ✓
Result: true ✓
Triplet: [2, 3, 4] at indices (0, 2, 3) ✓
Why this works:
We found a BETTER second value (3 instead of 5)
This gives us more room for third value! ✓
Edge Case 4: The Tricky One - Why It Still Works
nums = [1, 5, 0, 4, 1, 3]
Trace:
i=0, num=1: first = 1
i=1, num=5: second = 5 (pair: [1, 5])
i=2, num=0: first = 0 (second still = 5)
OLD pair [1, 5] still exists!
i=3, num=4: 4 > first(0)? YES, 4 <= second(5)? YES
→ second = 4 (pair: [0, 4])
i=4, num=1: 1 > first(0)? YES, 1 <= second(4)? YES
→ second = 1 (pair: [0, 1])
i=5, num=3: 3 > second(1)? YES → Found! ✓
Result: true ✓
Which triplet?
Could be [0, 1, 3] at indices (2, 4, 5) ✓
But wait! Is there an earlier triplet?
YES! [1, 5, ...] but we never found third > 5
With our updates, we found [0, 1, 3] ✓
The algorithm is GREEDY:
It finds SOME triplet, not necessarily the first! ✓
But that's okay - we only need to know IF one exists! ✓
📊 Complexity Analysis
All Approaches Compared
┌──────────────────┬─────────────┬──────────────┬──────────────┐
│ Approach │ Time │ Space │ Practical? │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ Brute Force │ O(n³) │ O(1) │ NO ❌ │
│ (Approach 1) │ Cubic │ None │ Way too slow │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ LIS Solution │ O(n log n) │ O(1) │ YES ✓ │
│ (Approach 2) │ Linearithmic│ Constant │ Good │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ Two Variables │ O(n) │ O(1) │ YES ✓ │
│ (Approach 3) │ Linear │ Constant │ Optimal │
└──────────────────┴─────────────┴──────────────┴──────────────┘
n = length of nums array
Detailed Time Complexity
APPROACH 1 - Brute Force O(n³):
Three nested loops: i, j, k
Each can go up to n
Total: n × n × n = O(n³) ❌
For n = 500,000:
125 × 10^15 operations
Completely impractical! ❌
APPROACH 2 - LIS Binary Search O(n log n):
For each element: binary search in tails array
Binary search: O(log 3) = O(1) (at most 3 elements)
But in general LIS: O(log n)
Total: O(n log n) ✓
For n = 500,000:
~9.5 million operations
Fast enough! ✓
Note: We optimize by returning early when size >= 3
APPROACH 3 - Two Variables O(n):
Single pass through array
Each element: O(1) operations
Total: O(n) ✓
For n = 500,000:
500,000 operations
Blazing fast! 🚀
This is OPTIMAL - can't do better than O(n)
because we must look at each element at least once! ✓
Detailed Space Complexity
APPROACH 1 - Brute Force:
No extra space, just loop variables
Total: O(1) ✓
APPROACH 2 - LIS Solution:
Tails array: at most 3 elements
Total: O(1) ✓
Technically O(3) = O(1) constant space!
APPROACH 3 - Two Variables:
Two variables: first and second
Total: O(1) ✓
Truly O(1) - just two integers!
All approaches use constant space! ✓
🎯 Pattern Recognition
The Triplet Pattern Family
INCREASING TRIPLET VARIATIONS:
1. Problem 248: Increasing Triplet Subsequence
Question: Does triplet exist?
Answer: Boolean
Optimal: O(n) time, O(1) space
This problem! ✓
2. Count Increasing Triplets (Not on LeetCode):
Question: How many triplets?
Answer: Count
Solution: O(n²) or O(n log n) with data structures
3. Longest Increasing Triplet Sum:
Question: Maximum sum of increasing triplet
Answer: Maximum value
Solution: Similar two-variable approach
4. K-Increasing Subsequence:
Question: Does length-k increasing subsequence exist?
Answer: Boolean
Solution: Generalize to k variables!
Common pattern:
- Looking for specific length subsequence
- Can optimize if length is small constant
- Two-variable pattern works for triplet (k=3)
From LIS to Triplet - The Optimization Journey
LONGEST INCREASING SUBSEQUENCE (ANY LENGTH):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Need to find: Subsequence of any length k
Must track: All possible lengths
Solution: DP array or tails array
Complexity: O(n²) or O(n log n)
INCREASING TRIPLET (LENGTH EXACTLY 3):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Need to find: Subsequence of length 3 only
Must track: Only 2 values (for first two elements)
Solution: Two variables
Complexity: O(n) time, O(1) space! 🚀
The optimization:
General case: O(n log n) with array
Special case (k=3): O(n) with two variables
This is the power of SPECIALIZED algorithms! 🔑
Can we generalize for any k?
For small constant k: Yes! Use k-1 variables
For large k: No! Need array-based solution
When To Recognize This Pattern
TRIGGER WORDS:
✓ "Increasing triplet"
✓ "Three increasing numbers"
✓ "Subsequence of length 3"
✓ "i < j < k and nums[i] < nums[j] < nums[k]"
PROBLEM STRUCTURE:
- Single array
- Looking for specific length (3)
- Increasing order
- Boolean answer (exists or not)
SOLUTION APPROACHES:
1. Brute Force: Try all triplets → O(n³)
2. Use LIS: Binary search → O(n log n)
3. Two Variables: Greedy → O(n) ✓
For triplet: Always use two variables! 🎯
For general k-tuple:
- Small k (k ≤ 5): Use k-1 variables
- Large k: Use LIS approach
💻 Complete Working Code
class Solution {
// Approach 1: Brute Force O(n³) - Don't use in interview!
public boolean increasingTriplet_BruteForce(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] < nums[j] && nums[j] < nums[k]) {
return true;
}
}
}
}
return false;
}
// Approach 2: LIS Binary Search O(n log n) - Good solution
public boolean increasingTriplet_LIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
tails.add(num);
} else {
tails.set(pos, num);
}
// Early termination
if (tails.size() >= 3) {
return true;
}
}
return false;
}
private int binarySearch(List<Integer> tails, int num) {
int left = 0;
int right = tails.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < num) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
// Approach 3: Two Variables O(n) - OPTIMAL! Use this in interview!
public boolean increasingTriplet(int[] nums) {
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= first) {
first = num;
} else if (num <= second) {
second = num;
} else {
return true;
}
}
return false;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.increasingTriplet(new int[] {1, 2, 3, 4, 5})); // true
System.out.println(sol.increasingTriplet(new int[] {5, 4, 3, 2, 1})); // false
System.out.println(sol.increasingTriplet(new int[] {2, 1, 5, 0, 4, 6})); // true
System.out.println(sol.increasingTriplet(new int[] {20, 100, 10, 12, 5, 13})); // true
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What is increasing triplet?
✓ Connection to LIS (special case!)
✓ Why can we optimize for k=3?
✓ Understanding two-variable pattern
WALK (Building):
✓ Brute force approach
✓ Applying LIS knowledge
✓ Discovering greedy optimization
✓ Why greedy is correct
RUN (Mastery):
✓ Two-variable optimal solution
✓ Mathematical proof of correctness
✓ Edge cases and tricky examples
✓ Why first can change (crucial insight!)
✓ Complete implementation
Natural baby-to-expert progression! 🎯
The Core Understanding
1. WHY two variables?
We're tracking "smallest" and "second smallest"
Only need TWO to detect THREE!
2. WHAT do they represent?
first = smallest value so far
second = smallest value > first so far
3. HOW does it work?
Keep updating to maintain invariant
When we find num > second, done!
4. WHEN does first change break things?
IT DOESN'T! Old pairs still exist!
We're just finding better candidates!
5. WHERE is the magic?
Greedy: Always keep best candidates
If triplet exists, we'll find it! 🔑
Mental Model
Think of it as TRACKING TWO SLOTS:
Slot 1 (first): Smallest number seen
→ Potential first element of triplet
Slot 2 (second): Smallest number > first
→ Potential second element of triplet
Slot 3 (current): Current number being checked
→ If > second, it's the third element! ✓
Visual:
[first] < [second] < [???]
↓ ↓ ↓
Keep Keep Looking
updating updating for this!
When current > second:
We found the third piece! ✓
📝 Quick Revision
🎯 Core Concept
Triplet = Special case of LIS with k=3
Two variables track two elements
Third element triggers success
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public boolean increasingTriplet(int[] a) {
if (a.length < 3) {
return false;
}
// return recursive_naive(a);
// // using LIS concept
// return lengthOfLIS(a) >= 3;
return optimal(a);
}
private boolean optimal(int[] a) {
// using 3 variables
int first = Integer.MAX_VALUE;
int second = Integer.MAX_VALUE;
for (int num : a) {
// Aim is as soon as we find num > second (got a triplet), return true
// Till that time, fill first and second.
if (num > second) {
return true;
} else if (num > first) {
second = num;
} else {
first = num;
}
}
return false;
}
private boolean recursive_naive(int[] a) {
int len = a.length;
// generate every triplet
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
for (int k = j + 1; k < len; k++) {
if (a[i] < a[j] && a[j] < a[k]) {
return true;
}
}
}
}
return false;
}
public int lengthOfLIS(int[] a) {
// return recursive(a, 0, Integer.MIN_VALUE);
// Integer[][] memo = new Integer[a.length + 1][a.length + 1];
// return topDown(a, 0, -1, memo);
// return bottomUp(a);
return bs(a);
}
private int bs(int[] a) {
List<Integer> tails = new ArrayList<>();
for (int num : a) {
// Binary search for position
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
// Create new pile (means incoming number is
// greater than all the current elements of the list)
tails.add(num);
} else {
// Replace pile top
tails.set(pos, num);
}
}
return tails.size();
}
// returns position (leftmost) where tails[pos] >= num
private int binarySearch(List<Integer> tails, int num) {
int left = 0;
int right = tails.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < num) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int bottomUp(int[] a) {
int len = a.length;
int[] dp = new int[len];
// dp[i] = length of longest increasing subsequence ENDING at index i
// dp[i] stores the best we can do if we MUST include nums[i]
// By default, for any array, LIS is 1.
Arrays.fill(dp, 1);
for (int i = 1; i < a.length; i++) {
for (int j = 0; j < i; j++) {
if (a[i] > a[j]) {
// [10,9,2,5,3,7,101,18]
// [1,1,1,....]
// for i = 3 where j = 0 to 2 => dp[3]=2
// incremental result calculation
// 1+dp[j] means length of sequence till that
// plus 1 including the current element
dp[i] = Math.max(dp[i], 1 + dp[j]);
}
}
}
return Arrays.stream(dp).max().getAsInt();
}
private int topDown(int[] a, int i, int prevMaxIndex, Integer[][] memo) {
if (i == a.length) {
return 0;
}
if (memo[i][prevMaxIndex + 1] != null) {
return memo[i][prevMaxIndex + 1];
}
int skip = topDown(a, i + 1, prevMaxIndex, memo);
int take = 0;
// GOTCHA
if (prevMaxIndex == -1 || a[i] > a[prevMaxIndex]) {
take = 1 + topDown(a, i + 1, i, memo);
}
return memo[i][prevMaxIndex + 1] = Math.max(skip, take);
}
private int recursive(int[] a, int i, int prevMax) {
// step 3: base case
if (i == a.length) {
return 0;
}
// step 1: skip the current element at index i
// if skip, go to next index and prev will be old prev only.
int skip = recursive(a, i + 1, prevMax);
// step 2: consider the current element at index i only
// when its greater than the previous element
// Since we are considering the current element, we have to update prev element
// to the current element for the next call that is going to happen.
// Also, since considering, we have to increase the length of LIS.
int take = 0;
if (a[i] > prevMax) {
take = 1 + recursive(a, i + 1, a[i]);
}
return Math.max(skip, take);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.increasingTriplet(new int[] { 1, 2, 3, 4, 5 }) == true);
System.out.println(s.increasingTriplet(new int[] { 5, 4, 3, 2, 1 }) == false);
System.out.println(s.increasingTriplet(new int[] { 2, 1, 5, 0, 4, 6 }) == true);
}
}
🎪 Memory Aid
"Two slots for two elements"
"Third greater means success"
"Keep updating to stay greedy"
Complexity: O(n) time, O(1) space - OPTIMAL! ✓
🎉 Congratulations!
You've mastered through baby steps: - ✅ CRAWL: Understanding triplet as LIS special case - ✅ WALK: From brute force to LIS to greedy - ✅ RUN: Optimal two-variable solution - ✅ Mathematical proof of correctness - ✅ Crucial insight: why first can change - ✅ All edge cases explained - ✅ Three complete approaches - ✅ True comprehensive understanding
You've learned how SPECIALIZATION enables OPTIMIZATION with textbook-style learning! 🚀✨
KEY TAKEAWAY: When problem asks for specific small k, you can often optimize from general O(n log n) LIS to O(n) with k-1 variables! 🔑