247. Longest Increasing Subsequence
🔗 LeetCode Problem: 300. Longest Increasing Subsequence
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Binary Search, Array, DP - LIS
Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
Follow up: Can you come up with an algorithm that runs in O(n log n) time complexity?
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "longest increasing subsequence" for a moment. Let me understand:
Given: nums = [10,9,2,5,3,7,101,18]
Question: Find longest sequence where each number is BIGGER than previous?
Let me try to find sequences manually:
Sequence 1: [10] → length 1
Sequence 2: [9] → length 1
Sequence 3: [2] → length 1
Sequence 4: [2, 5] → length 2 ✓ (5 > 2)
Sequence 5: [2, 5, 7] → length 3 ✓ (5 > 2, 7 > 5)
Sequence 6: [2, 5, 7, 101] → length 4 ✓ (each bigger than previous!)
Sequence 7: [2, 3, 7, 101] → length 4 ✓ (another way!)
Sequence 8: [2, 3, 7, 18] → length 4 ✓ (yet another way!)
Can I find length 5? Let me try...
After 7, next is 101 (too big jump)
After 7, next is 18 (works, but no more after)
Can't find length 5! Maximum seems to be 4 ✓
KEY INSIGHT: Find the LONGEST strictly increasing sequence! 🔑
Understanding Subsequences
What is a subsequence again?
A subsequence is formed by DELETING some (or no) elements
WITHOUT changing the order of remaining elements.
Example: nums = [10,9,2,5,3,7,101,18]
All subsequences include:
[10]
[10,9]
[10,2]
[10,5]
...
[2,5,7,101]
[2,3,7,18]
... many more!
But we want INCREASING subsequences only:
[10,101] ✓ (10 < 101)
[9,101] ✓ (9 < 101)
[2,5,7,101] ✓ (2 < 5 < 7 < 101)
[10,9] ✗ (10 > 9, not increasing!)
[7,7,7] ✗ (not STRICTLY increasing!)
IMPORTANT: "Strictly" means each element must be BIGGER (not equal)! 🔑
Why Is This Different From LCS?
Let me compare with Longest Common Subsequence:
LONGEST COMMON SUBSEQUENCE (LCS):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Input: TWO strings
Goal: Find longest common subsequence
Pattern: 2D DP (dp[i][j])
Comparison: Between two sequences
Example:
str1 = "abcde"
str2 = "ace"
LCS = "ace" (length 3)
LONGEST INCREASING SUBSEQUENCE (LIS):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Input: ONE array
Goal: Find longest increasing subsequence
Pattern: 1D DP (dp[i]) ← NEW!
Comparison: Within same sequence
Example:
nums = [10,9,2,5,3,7,101,18]
LIS = [2,3,7,101] (length 4)
KEY DIFFERENCE:
LCS: Compare TWO sequences (2D DP)
LIS: Compare within ONE sequence (1D DP)! 🔑
This is a COMPLETELY NEW pattern! 🎯
🤔 Building Intuition - The 1D DP Pattern
Understanding The Core Question
For each position i, I want to ask:
"What's the longest increasing subsequence ENDING at position i?"
Let me trace this for: nums = [10,9,2,5,3,7,101,18]
Position 0 (value 10):
LIS ending here: [10]
Length: 1
Position 1 (value 9):
Can I extend from position 0?
9 < 10? NO ✗
LIS ending here: [9]
Length: 1
Position 2 (value 2):
Can I extend from position 0? 2 < 10? NO ✗
Can I extend from position 1? 2 < 9? NO ✗
LIS ending here: [2]
Length: 1
Position 3 (value 5):
Can I extend from position 0? 5 < 10? NO ✗
Can I extend from position 1? 5 < 9? NO ✗
Can I extend from position 2? 5 > 2? YES! ✓
Can extend [2] → [2,5]
LIS ending here: [2,5]
Length: 2
Position 4 (value 3):
Can I extend from position 0? 3 < 10? NO ✗
Can I extend from position 1? 3 < 9? NO ✗
Can I extend from position 2? 3 > 2? YES! ✓
Can extend [2] → [2,3]
Can I extend from position 3? 3 < 5? NO ✗
LIS ending here: [2,3]
Length: 2
Position 5 (value 7):
Can extend from position 2? 7 > 2? YES! ✓ → length 2
Can extend from position 3? 7 > 5? YES! ✓ → length 3 ← Better!
Can extend from position 4? 7 > 3? YES! ✓ → length 3 ← Same!
LIS ending here: [2,5,7] or [2,3,7]
Length: 3
Position 6 (value 101):
Can extend from position 5? 101 > 7? YES! ✓ → length 4
LIS ending here: [2,5,7,101] or [2,3,7,101]
Length: 4
Position 7 (value 18):
Can extend from position 5? 18 > 7? YES! ✓ → length 4
Can extend from position 6? 18 < 101? NO ✗
LIS ending here: [2,5,7,18] or [2,3,7,18]
Length: 4
Global maximum: 4 ✓
INSIGHT: For each position, check ALL previous positions! 🔑
The Key Insight - Compare With All Previous
To find LIS ending at position i:
Look at ALL positions j where j < i:
If nums[j] < nums[i]:
Can extend the LIS ending at j!
New length = LIS[j] + 1
Take the MAXIMUM among all possible extensions!
Example: Position 5 (value 7)
j=0 (value 10): 10 < 7? NO, skip
j=1 (value 9): 9 < 7? NO, skip
j=2 (value 2): 2 < 7? YES!
LIS[2] = 1
Can make length = 1 + 1 = 2
j=3 (value 5): 5 < 7? YES!
LIS[3] = 2
Can make length = 2 + 1 = 3 ← Better!
j=4 (value 3): 3 < 7? YES!
LIS[4] = 2
Can make length = 2 + 1 = 3
Maximum: 3
LIS[5] = 3
This is the CORE algorithm! ✓
Why This Is Different From 2D String DP
STRING DP (LCS, Edit Distance, etc.):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Pattern: dp[i][j]
Meaning: Relationship between s[0..i] and t[0..j]
Comparison: Between TWO different strings
Loops: Two nested loops over BOTH strings
for i in range(m):
for j in range(n):
compare s[i] with t[j]
ARRAY DP (LIS):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Pattern: dp[i]
Meaning: Property of subsequence ending at i
Comparison: Element at i with ALL previous elements
Loops: Two nested loops over SAME array
for i in range(n):
for j in range(i):
compare nums[i] with nums[j]
KEY DIFFERENCE:
String DP: i and j are from different strings
Array DP: i and j are from SAME array! 🔑
This is why we can use 1D DP! ✓
🔴 Approach 1: Pure Recursion - Understanding the Pattern
The Recursive Insight
Define: LIS(i) = length of longest increasing subsequence
using elements from nums[0..i]
But wait! This doesn't work! 🤔
Problem: LIS(i) doesn't have enough information!
We need to know: what was the LAST element chosen?
Better definition:
Define: LIS(i, prev) = length of LIS from nums[i..]
where prev is the last chosen element
Base case:
If i == n: return 0 (no more elements)
Recursive cases:
Choice 1: SKIP nums[i]
Don't include current element
LIS(i+1, prev)
Choice 2: TAKE nums[i] (only if nums[i] > prev)
Include current element
1 + LIS(i+1, nums[i])
Return MAXIMUM of valid choices!
This is similar to previous problems! ✓
Implementation
class Solution {
public int lengthOfLIS(int[] nums) {
return lisHelper(nums, 0, Integer.MIN_VALUE);
}
private int lisHelper(int[] nums, int i, int prev) {
// Base case: reached end
if (i == nums.length) {
return 0;
}
// Choice 1: Skip current element
int skip = lisHelper(nums, i + 1, prev);
// Choice 2: Take current element (if valid)
int take = 0;
if (nums[i] > prev) {
take = 1 + lisHelper(nums, i + 1, nums[i]);
}
return Math.max(skip, take);
}
}
Why This Is Too Slow
TIME COMPLEXITY ANALYSIS:
At each position, we make 2 recursive calls!
Recursion tree branches exponentially!
(0, -∞)
/ \
(1,-∞) (1,10)
/ \ / \
(2,-∞)(2,9) (2,9)(2,10)
↑ ↑
Different prev values!
Number of unique states: n × (number of distinct values)
But exponential branching!
Worst case: O(2^n) ❌
For nums = [1,2,3,4,5,6,7,8,9,10] (10 elements)
2^10 = 1024 branches! ❌
OBSERVATION:
We recompute same (i, prev) multiple times!
Overlapping subproblems!
This needs MEMOIZATION! 🔑
🟡 Approach 1.5: Top-Down Memoization (O(n²) Solution)
Understanding The Two-Parameter State
The challenge with memoizing Approach 1:
We had: lisHelper(i, prev)
- i: current index
- prev: previous value chosen
Problem: prev can be ANY value in the array!
Can't create memo[i][prev] easily!
Solution: Use INDEX instead of VALUE!
Better state:
lis(i, prevIndex) = length of LIS from index i onwards
where prevIndex is the last chosen element
Special case: prevIndex = -1 means no element chosen yet
Now we can memoize: memo[i][prevIndex+1]
(Add 1 to prevIndex because it starts at -1)
The Memoized Recursive Logic
State: lis(i, prevIndex)
i = current position we're considering
prevIndex = index of last element we chose (-1 if none)
Base case:
if i == n: return 0 (no more elements)
Recursive cases:
Choice 1: SKIP current element
lis(i+1, prevIndex)
(Move to next, keep same previous)
Choice 2: TAKE current element (if valid)
Only if: prevIndex == -1 OR nums[i] > nums[prevIndex]
1 + lis(i+1, i)
(Add 1, update previous to current index)
Return: max(skip, take)
Why this works:
- We track INDICES not VALUES
- Can create 2D memo table: (n+1) × (n+1)
- prevIndex ranges from -1 to n-1
- Store in memo[i][prevIndex+1]
Detailed Example Walkthrough
Example: nums = [10,9,2,5,3,7]
Let me trace: lis(0, -1) [starting position, no previous]
lis(0, -1)
nums[0]=10
SKIP / \ TAKE
lis(1,-1) lis(1,0)
nums[1]=9 nums[1]=9, prev=10
SKIP/ \TAKE SKIP/ \TAKE? 9>10? NO
lis(2,-1) lis(2,1) lis(2,0) X
nums[2]=2 prev=9 prev=10
/ \ / \ / \
SKIP TAKE SKIP TAKE SKIP TAKE? 2>10? NO
lis(3,-1) ... lis(3,0) X
Eventually finds: [2,3,7] with length 3
The recursion explores all valid paths!
Memoization prevents recomputation! ✓
Complete Implementation
class Solution {
private Integer[][] memo;
public int lengthOfLIS(int[] nums) {
int n = nums.length;
// memo[i][prevIndex+1] to handle prevIndex=-1
memo = new Integer[n][n + 1];
return lisHelper(nums, 0, -1);
}
private int lisHelper(int[] nums, int i, int prevIndex) {
// Base case: reached end
if (i == nums.length) {
return 0;
}
// Check memo (shift prevIndex by 1 for array indexing)
if (memo[i][prevIndex + 1] != null) {
return memo[i][prevIndex + 1];
}
// Choice 1: Skip current element
int skip = lisHelper(nums, i + 1, prevIndex);
// Choice 2: Take current element (if valid)
int take = 0;
if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
take = 1 + lisHelper(nums, i + 1, i);
}
// Store and return best choice
int result = Math.max(skip, take);
memo[i][prevIndex + 1] = result;
return result;
}
}
Why Top-Down Works But Is Less Common
ADVANTAGES of Top-Down:
✓ Natural recursive thinking
✓ Only computes needed states
✓ Easier to understand for some people
✓ Same O(n²) complexity as bottom-up
DISADVANTAGES of Top-Down:
✗ Need to track TWO parameters (i and prevIndex)
✗ Memo table is larger: n × (n+1) vs just n
✗ Call stack overhead: O(n) space
✗ Slightly slower due to function calls
✗ Less intuitive what memo[i][j] represents
WHY Bottom-Up is Preferred for LIS:
The bottom-up approach (Approach 2) uses:
dp[i] = LIS ending at i
This is MORE INTUITIVE:
- Only one dimension
- Clear meaning: "best ending here"
- Easier to optimize to O(n log n)
Top-down uses:
memo[i][prevIndex+1] = LIS from i with prev
This is LESS INTUITIVE:
- Two dimensions
- Complex meaning: "best from i given prev"
- Harder to see binary search optimization
For LIS specifically, bottom-up is the standard! ✓
Comparison: Top-Down vs Bottom-Up
┌─────────────────┬──────────────┬────────────────┐
│ Aspect │ Top-Down │ Bottom-Up │
├─────────────────┼──────────────┼────────────────┤
│ DP State │ 2D (i, prev) │ 1D (i) │
│ Memo Size │ n × (n+1) │ n │
│ Space │ O(n²)+stack │ O(n) │
│ Time │ O(n²) │ O(n²) │
│ Intuitive? │ Less ✗ │ More ✓ │
│ Optimizable? │ Harder │ Easier │
│ Standard? │ No │ YES ✓ │
└─────────────────┴──────────────┴────────────────┘
For LIS: Bottom-up is the way to go! 🎯
Visual: Why Two Parameters Needed
Consider: nums = [3, 1, 4, 2]
Without tracking previous:
At index 2 (value 4):
Can we take it?
Depends on what we chose before!
If we chose 3: 3 < 4? YES ✓ → [3,4]
If we chose 1: 1 < 4? YES ✓ → [1,4]
Different paths, different results!
With tracking previous:
lis(2, 0) = LIS from 2 with prev=0 (value 3)
Can take 4 → [3,4]
lis(2, 1) = LIS from 2 with prev=1 (value 1)
Can take 4 → [1,4]
Different states, properly memoized! ✓
This is why we need prevIndex! 🔑
Converting Top-Down Thinking to Bottom-Up
Top-Down Mindset:
"From position i with previous choice prev,
what's the best I can do?"
Bottom-Up Mindset:
"If I MUST end at position i,
what's the best I can do?"
The shift:
Top-Down: Look FORWARD from i
Bottom-Up: Look BACKWARD to i
Example at position i=5 (value 7):
Top-Down asks:
"From 5 onwards, with prev=3 (value 5),
what's the longest sequence?"
Bottom-Up asks:
"What's the longest sequence ENDING at 5?"
"Can I extend from position 3? Yes! 5 < 7"
"Can I extend from position 4? Yes! 3 < 7"
Take best extension!
Both compute the same thing, different angles! ✓
🟢 Approach 3: Bottom-Up DP (O(n²) Solution) - Standard Solution
Understanding The DP State
Let me think about the DP definition:
dp[i] = length of longest increasing subsequence ENDING at index i
What this means:
- dp[i] stores the best we can do if we MUST include nums[i]
- It's the longest sequence that ends with nums[i]
- Answer is max(dp[0], dp[1], ..., dp[n-1])
Examples:
nums = [10,9,2,5,3,7,101,18]
dp[0] = 1 (just [10])
dp[1] = 1 (just [9])
dp[2] = 1 (just [2])
dp[3] = 2 ([2,5])
dp[4] = 2 ([2,3])
dp[5] = 3 ([2,5,7])
dp[6] = 4 ([2,5,7,101])
dp[7] = 4 ([2,5,7,18])
Answer = max(dp) = 4 ✓
This is our DP definition! ✓
Building The DP Array - Understanding Each Cell
Let me build for: nums = [10,9,2,5,3,7,101,18]
Initial state: All dp[i] = 1 (each element alone is length 1)
dp = [1, 1, 1, 1, 1, 1, 1, 1]
PHASE 1: Process Each Position
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Position 0 (value 10):
No previous elements
dp[0] = 1
Position 1 (value 9):
Check j=0 (value 10):
9 > 10? NO ✗
dp[1] = 1
Position 2 (value 2):
Check j=0 (value 10): 2 > 10? NO ✗
Check j=1 (value 9): 2 > 9? NO ✗
dp[2] = 1
Position 3 (value 5):
Check j=0 (value 10): 5 > 10? NO ✗
Check j=1 (value 9): 5 > 9? NO ✗
Check j=2 (value 2): 5 > 2? YES! ✓
Can extend: dp[2] + 1 = 1 + 1 = 2
dp[3] = 2
dp = [1, 1, 1, 2, 1, 1, 1, 1]
Position 4 (value 3):
Check j=0 (value 10): 3 > 10? NO ✗
Check j=1 (value 9): 3 > 9? NO ✗
Check j=2 (value 2): 3 > 2? YES! ✓
Can extend: dp[2] + 1 = 1 + 1 = 2
Check j=3 (value 5): 3 > 5? NO ✗
dp[4] = 2
dp = [1, 1, 1, 2, 2, 1, 1, 1]
Position 5 (value 7):
Check j=0 (value 10): 7 > 10? NO ✗
Check j=1 (value 9): 7 > 9? NO ✗
Check j=2 (value 2): 7 > 2? YES! ✓
Can extend: dp[2] + 1 = 1 + 1 = 2
Check j=3 (value 5): 7 > 5? YES! ✓
Can extend: dp[3] + 1 = 2 + 1 = 3 ← Better!
Check j=4 (value 3): 7 > 3? YES! ✓
Can extend: dp[4] + 1 = 2 + 1 = 3
Best: 3
dp[5] = 3
dp = [1, 1, 1, 2, 2, 3, 1, 1]
Position 6 (value 101):
Check all j < 6:
101 > 10? YES → dp[0]+1 = 2
101 > 9? YES → dp[1]+1 = 2
101 > 2? YES → dp[2]+1 = 2
101 > 5? YES → dp[3]+1 = 3
101 > 3? YES → dp[4]+1 = 3
101 > 7? YES → dp[5]+1 = 4 ← Best!
dp[6] = 4
dp = [1, 1, 1, 2, 2, 3, 4, 1]
Position 7 (value 18):
Check all j < 7:
18 > 10? YES → dp[0]+1 = 2
18 > 9? YES → dp[1]+1 = 2
18 > 2? YES → dp[2]+1 = 2
18 > 5? YES → dp[3]+1 = 3
18 > 3? YES → dp[4]+1 = 3
18 > 7? YES → dp[5]+1 = 4 ← Best!
18 > 101? NO ✗
dp[7] = 4
dp = [1, 1, 1, 2, 2, 3, 4, 4]
FINAL ANSWER: max(dp) = 4 ✓
The DP Recurrence - Complete Understanding
For dp[i], we're asking:
What's the longest increasing subsequence ENDING at i?
Initialization:
dp[i] = 1 for all i
(Each element alone is a valid subsequence)
For each position i:
For each previous position j where j < i:
If nums[j] < nums[i]:
Can extend the sequence ending at j!
New length = dp[j] + 1
Update: dp[i] = max(dp[i], dp[j] + 1)
Final answer: max(dp[0], dp[1], ..., dp[n-1])
This is the complete DP recurrence! ✓
Why this works:
- We process positions left to right
- When we reach position i, all dp[j] (j < i) are computed
- We try extending from ALL previous valid positions
- Take the BEST extension!
Beautiful! ✓
Complete Implementation
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
// dp[i] = length of LIS ending at index i
int[] dp = new int[n];
// Initialize: each element alone is length 1
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// For each position
for (int i = 1; i < n; i++) {
// Check all previous positions
for (int j = 0; j < i; j++) {
// Can we extend from j?
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// Find maximum among all dp values
int maxLength = 0;
for (int length : dp) {
maxLength = Math.max(maxLength, length);
}
return maxLength;
}
}
🚀 Approach 4: Binary Search + DP (O(n log n) Solution) - Optimal
The Brilliant Insight - Patience Sorting
Here's a COMPLETELY DIFFERENT way to think about LIS!
Imagine playing a card game:
- You have piles of cards
- Cards in each pile are in DECREASING order (top to bottom)
- When you get a new card, place it on the LEFTMOST pile
where it's SMALLER than the top card
- If no such pile exists, create a NEW pile
The number of piles = LIS length! 🎯
Example: nums = [10,9,2,5,3,7,101,18]
Card 10:
Piles: [10]
Count: 1
Card 9:
9 < 10? YES → place on pile 1
Piles: [9] (10 below)
Count: 1
Card 2:
2 < 9? YES → place on pile 1
Piles: [2] (9,10 below)
Count: 1
Card 5:
5 < 2? NO → need new pile
Piles: [2], [5]
Count: 2
Card 3:
3 < 2? NO
3 < 5? YES → place on pile 2
Piles: [2], [3] (5 below)
Count: 2
Card 7:
7 < 2? NO
7 < 3? NO → need new pile
Piles: [2], [3], [7]
Count: 3
Card 101:
101 < 2? NO
101 < 3? NO
101 < 7? NO → need new pile
Piles: [2], [3], [7], [101]
Count: 4
Card 18:
18 < 2? NO
18 < 3? NO
18 < 7? NO
18 < 101? YES → place on pile 4
Piles: [2], [3], [7], [18] (101 below)
Count: 4
Final: 4 piles = LIS length 4! ✓
WHY does this work? 🤔
Why Patience Sorting Works - The Proof
THEOREM: Number of piles = Length of LIS
PROOF:
Part 1: Number of piles ≤ LIS length
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Suppose LIS has length k.
If we had more than k piles:
By pigeonhole principle, at least one pile
would have more than one element from the LIS.
But elements in a pile are DECREASING!
This contradicts LIS being INCREASING!
Therefore: piles ≤ k ✓
Part 2: Number of piles ≥ LIS length
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
We can construct an increasing subsequence:
Take the TOP card from each pile!
Example from above:
Pile 1 top: 2
Pile 2 top: 3
Pile 3 top: 7
Pile 4 top: 18
Sequence: [2, 3, 7, 18]
Is this increasing?
When we placed card on pile i+1,
it was bigger than top of pile i!
So: pile[i].top < pile[i+1].top ✓
This gives us an increasing subsequence
of length = number of piles!
Therefore: piles ≥ LIS length ✓
Combining: piles = LIS length! QED ✓
This is BEAUTIFUL mathematics! ✓
Using Binary Search To Find Pile
Key insight: Pile tops are in INCREASING order!
Why?
Pile 1 has smallest top (smallest card placed there)
Pile 2 has larger top (couldn't fit on pile 1)
Pile 3 has larger top (couldn't fit on piles 1,2)
And so on...
Since pile tops are sorted:
We can use BINARY SEARCH to find the leftmost pile! ✓
Algorithm:
tails = [] (array of pile tops)
for each num in nums:
// Find leftmost pile where num < pile.top
pos = binary_search(tails, num)
if pos == len(tails):
// No pile found, create new pile
tails.append(num)
else:
// Place on existing pile
tails[pos] = num
return len(tails)
Time: O(n log n) ✓
- n iterations
- Each binary search is O(log n)
Complete Binary Search Implementation
class Solution {
public int lengthOfLIS(int[] nums) {
// tails[i] = smallest tail of all increasing subsequences of length i+1
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
// Binary search for position
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
// Create new pile
tails.add(num);
} else {
// Replace pile top
tails.set(pos, num);
}
}
return tails.size();
}
// Find leftmost position 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;
}
}
Why Binary Search Version Is Optimal
COMPLEXITY COMPARISON:
DP Approach (Approach 2):
Time: O(n²)
- Outer loop: n iterations
- Inner loop: up to n iterations
- Total: n × n = n²
Space: O(n)
- DP array of size n
Binary Search Approach (Approach 3):
Time: O(n log n) ✓
- Outer loop: n iterations
- Binary search: O(log n) per iteration
- Total: n × log n
Space: O(n)
- Tails array (at most n elements)
For n = 2500 (max constraint):
O(n²) = 6,250,000 operations
O(n log n) = 27,500 operations
Binary search is ~225x faster! 🚀
For large inputs, this makes the difference
between TLE and AC! ✓
🔍 Detailed Example - Both Approaches
Example: nums = [0,1,0,3,2,3]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
APPROACH 3: O(n²) Bottom-Up DP
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Initial: dp = [1, 1, 1, 1, 1, 1]
i=0 (value 0):
No previous elements
dp[0] = 1
i=1 (value 1):
j=0 (value 0): 1 > 0? YES → dp[0]+1 = 2
dp[1] = 2
dp = [1, 2, 1, 1, 1, 1]
i=2 (value 0):
j=0 (value 0): 0 > 0? NO
j=1 (value 1): 0 > 1? NO
dp[2] = 1
dp = [1, 2, 1, 1, 1, 1]
i=3 (value 3):
j=0 (value 0): 3 > 0? YES → dp[0]+1 = 2
j=1 (value 1): 3 > 1? YES → dp[1]+1 = 3 ← Best!
j=2 (value 0): 3 > 0? YES → dp[2]+1 = 2
dp[3] = 3
dp = [1, 2, 1, 3, 1, 1]
i=4 (value 2):
j=0: 2 > 0? YES → 2
j=1: 2 > 1? YES → 3 ← Best!
j=2: 2 > 0? YES → 2
j=3: 2 > 3? NO
dp[4] = 3
dp = [1, 2, 1, 3, 3, 1]
i=5 (value 3):
j=0: 3 > 0? YES → 2
j=1: 3 > 1? YES → 3
j=2: 3 > 0? YES → 2
j=3: 3 > 3? NO
j=4: 3 > 2? YES → 4 ← Best!
dp[5] = 4
dp = [1, 2, 1, 3, 3, 4]
Answer: max(dp) = 4 ✓
The LIS: [0, 1, 2, 3]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
APPROACH 4: O(n log n) Binary Search
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
tails = []
Process 0:
Binary search for 0 in []
pos = 0
tails = [0]
Process 1:
Binary search for 1 in [0]
1 > 0, so pos = 1
tails = [0, 1]
Process 0:
Binary search for 0 in [0, 1]
0 >= 0, pos = 0
Replace: tails = [0, 1]
Process 3:
Binary search for 3 in [0, 1]
3 > 1, pos = 2
tails = [0, 1, 3]
Process 2:
Binary search for 2 in [0, 1, 3]
2 > 1 but 2 < 3, pos = 2
Replace: tails = [0, 1, 2]
Process 3:
Binary search for 3 in [0, 1, 2]
3 > 2, pos = 3
tails = [0, 1, 2, 3]
Answer: len(tails) = 4 ✓
Both approaches give the same answer! ✓
📊 Complexity Analysis
All Approaches Compared
┌──────────────────┬─────────────┬──────────────┬──────────────┐
│ Approach │ Time │ Space │ Practical? │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ Recursion │ O(2^n) │ O(n) │ NO ❌ │
│ (Approach 1) │ Exponential │ Stack │ Too slow │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ Top-Down Memo │ O(n²) │ O(n²) │ YES ✓ │
│ (Approach 1.5) │ Quadratic │ Memo+Stack │ Less common │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ Bottom-Up DP │ O(n²) │ O(n) │ YES ✓ │
│ (Approach 3) │ Quadratic │ DP array │ Standard │
├──────────────────┼─────────────┼──────────────┼──────────────┤
│ Binary Search │ O(n log n) │ O(n) │ YES ✓ │
│ (Approach 4) │ Linearithmic│ Tails array │ Optimal │
└──────────────────┴─────────────┴──────────────┴──────────────┘
n = length of nums array
Detailed Time Complexity
APPROACH 1 - Pure Recursion:
At each position:
Two choices (skip or take)
Two recursive calls
Branching factor: 2
Tree height: n
Total: O(2^n) ❌
For n = 10:
2^10 = 1024 calls! ❌
APPROACH 1.5 - Top-Down Memoization O(n²):
Number of unique states: n × (n+1)
(i ranges 0 to n-1, prevIndex ranges -1 to n-1)
Each state computed once: O(1) work
Total: O(n²) ✓
For n = 2500:
~6.25 million states ✓
Same time as bottom-up but more space (includes call stack)!
APPROACH 3 - Bottom-Up DP O(n²):
Outer loop: n iterations (i from 0 to n-1)
Inner loop: up to n iterations (j from 0 to i-1)
Total: 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²) ✓
For n = 2500:
~3.1 million operations ✓
Acceptable for most problems!
APPROACH 4 - Binary Search O(n log n):
Outer loop: n iterations
Binary search: O(log n) per iteration
Total: n × log n = O(n log n) ✓
For n = 2500:
~27,000 operations ✓
Much faster than O(n²)! 🚀
Detailed Space Complexity
APPROACH 1 - Recursion:
Call stack: O(n)
No extra arrays
Total: O(n)
APPROACH 1.5 - Top-Down Memoization:
Memo table: (n) × (n+1) integers
Size: O(n²)
Call stack: O(n)
Total: O(n²)
Note: Uses more space than bottom-up!
APPROACH 3 - Bottom-Up DP O(n²):
DP array: O(n)
Total: O(n) ✓
APPROACH 4 - Binary Search:
Tails array: O(n) in worst case
(When all elements are increasing)
Total: O(n) ✓
All have linear space complexity! ✓
🎯 Pattern Recognition
The LIS Pattern Family
LONGEST INCREASING SUBSEQUENCE VARIATIONS:
1. Problem 247: Longest Increasing Subsequence
Question: Length of LIS
This problem! ✓
2. Number of LIS (673):
Question: How many LIS exist?
Type: Counting
3. Russian Doll Envelopes (354):
Question: LIS in 2D
Trick: Sort + LIS
4. Maximum Length of Pair Chain (646):
Question: LIS with intervals
Greedy or DP
5. Longest String Chain (1048):
Question: LIS with string rules
DP + String manipulation
Common pattern:
- Finding optimal subsequence
- Elements must satisfy condition
- DP solution O(n²) or better
- Often optimizable with binary search
LIS vs LCS - Key Differences
LONGEST COMMON SUBSEQUENCE (LCS):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Input: TWO sequences
DP Table: 2D (dp[i][j])
Recurrence:
if s1[i] == s2[j]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
LONGEST INCREASING SUBSEQUENCE (LIS):
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Input: ONE sequence
DP Table: 1D (dp[i])
Recurrence:
for j < i:
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
KEY DIFFERENCE:
LCS: Compare across two sequences
LIS: Compare within same sequence! 🔑
When To Recognize This Pattern
TRIGGER WORDS:
✓ "Longest increasing subsequence"
✓ "Strictly increasing"
✓ "Maximum length"
✓ "Subsequence" (not substring!)
✓ "Increasing order"
PROBLEM STRUCTURE:
- Single array/sequence
- Find longest with property
- Elements must be in order
- Property: each > previous
SOLUTION APPROACHES:
1. DP O(n²):
for i from 0 to n:
for j from 0 to i:
if valid(j, i):
dp[i] = max(dp[i], dp[j] + 1)
2. Binary Search O(n log n):
Patience sorting / tails array
Choose based on:
- Small n (≤1000): O(n²) is fine
- Large n (>1000): Use O(n log n)
💻 Complete Working Code
class Solution {
// Approach 1.5: Top-Down Memoization O(n²)
public int lengthOfLIS_TopDown(int[] nums) {
int n = nums.length;
Integer[][] memo = new Integer[n][n + 1];
return lisHelper(nums, 0, -1, memo);
}
private int lisHelper(int[] nums, int i, int prevIndex, Integer[][] memo) {
if (i == nums.length) {
return 0;
}
if (memo[i][prevIndex + 1] != null) {
return memo[i][prevIndex + 1];
}
// Skip
int skip = lisHelper(nums, i + 1, prevIndex, memo);
// Take (if valid)
int take = 0;
if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
take = 1 + lisHelper(nums, i + 1, i, memo);
}
memo[i][prevIndex + 1] = Math.max(skip, take);
return memo[i][prevIndex + 1];
}
// Approach 3: Bottom-Up DP O(n²) - Standard and most intuitive
public int lengthOfLIS_DP(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
// Initialize
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// Fill DP array
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
// Find maximum
int max = 0;
for (int length : dp) {
max = Math.max(max, length);
}
return max;
}
// Approach 4: Binary Search O(n log n) - Optimal
public int lengthOfLIS(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);
}
}
return tails.size();
}
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;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.lengthOfLIS(new int[] {10, 9, 2, 5, 3, 7, 101, 18})); // 4
System.out.println(sol.lengthOfLIS(new int[] {0, 1, 0, 3, 2, 3})); // 4
System.out.println(sol.lengthOfLIS(new int[] {7, 7, 7, 7, 7, 7, 7})); // 1
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What is increasing subsequence?
✓ Why different from LCS? (1D vs 2D)
✓ Understanding the choices
✓ Manual tracing to build intuition
WALK (Building):
✓ DP approach O(n²)
✓ Understanding dp[i] definition
✓ Why check all previous positions
✓ Building DP array step by step
RUN (Mastery):
✓ Binary search optimization
✓ Patience sorting insight
✓ Mathematical proof
✓ O(n log n) implementation
✓ Pattern recognition
Natural baby-to-expert progression! 🎯
The Core Understanding
1. WHY 1D DP?
Compare within SAME array!
No need for 2D table!
2. WHAT is dp[i]?
Length of LIS ENDING at i
Must include nums[i]!
3. HOW to compute dp[i]?
Check ALL j < i
If nums[j] < nums[i]: extend!
4. WHEN to use binary search?
When n is large (>1000)
Patience sorting trick!
5. WHERE's the optimization?
Tails array is sorted!
Binary search finds position!
Mental Model
TWO WAYS TO THINK:
Model 1: DP Array
dp[i] = best we can do ending at i
Check all previous positions
Take maximum extension
Model 2: Patience Sorting
Piles of cards in decreasing order
Place card on leftmost valid pile
Number of piles = LIS length
Both models work! Choose what makes sense! ✓
📝 Quick Revision
🎯 Core Concept
1D DP → Compare within same array
dp[i] → LIS ending at position i
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
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.lengthOfLIS(new int[] { 10, 9, 2, 5, 3, 7, 101, 18 }) == 4);
System.out.println(s.lengthOfLIS(new int[] { 0, 1, 0, 3, 2, 3 }) == 4);
System.out.println(s.lengthOfLIS(new int[] { 7, 7, 7, 7, 7, 7, 7 }) == 1);
}
}
🔑 Key Patterns
DP Approach:
- Check all previous positions
- Extend if nums[j] < nums[i]
- Take maximum
Binary Search:
- Tails array is sorted
- Find leftmost position
- Replace or extend
🎪 Memory Aid
"One array, one dimension"
"Ending at i is the key"
"Binary search for speed"
Complexity: O(n²) or O(n log n)
🎉 Congratulations!
You've mastered through baby steps: - ✅ CRAWL: Understanding 1D DP pattern - ✅ WALK: Building DP solution O(n²) - ✅ RUN: Binary search optimization O(n log n) - ✅ All three approaches explained - ✅ Patience sorting insight - ✅ Mathematical proof included - ✅ Pattern recognition mastery - ✅ True comprehensive understanding
You've learned a COMPLETELY NEW DP pattern with textbook-style learning! 🚀✨