March 24
Longest Increasing Subsequence
How to start from O(n²) dynamic programming and reach the idea of smallest possible endings with binary search.
Dynamic Programming Intermediate 22 min TypeScript
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence may skip elements, but it must preserve relative order.
Example:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
One longest increasing subsequence is [2,3,7,101].
What to notice before coding
- The problem asks for a subsequence, not a subarray or substring.
- The answer asks only for the length, not the actual list.
- In the optimized version, `tails` helps measure the length, but it does not always represent one full real subsequence.
Common mistakes
- treating the problem as contiguous
- looking at `tails` and assuming it is always exactly the final answer
Step 1 - Do not confuse subsequence with contiguity
Here you can skip elements.
That changes the reading of the problem a lot.
In [10,9,2,5,3,7,101,18], the answer can use:
2- then
3 - then
7 - then
101
Even with other values in between.
Step 2 - Write the DP baseline
A strong baseline is:
dp[i]= best length ending atnums[i]
To compute dp[i], you look at every j < i.
If nums[j] < nums[i], you can extend the subsequence that ended at j.
Step 3 - Ask what really helps the future
If I have two subsequences with the same length, which one is better to keep?
The one that ends with the smaller value.
Because it leaves more room to grow later.
That is the key insight behind the stronger version.
Step 4 - Replace "best length by index" with "smallest ending by length"
The tails array stores:
- at each position, the smallest possible ending value for a subsequence of that size
When a new number arrives:
- if it is bigger than all endings, it increases the length
- otherwise, it replaces the first ending that is greater than or equal to it
That replacement is exactly what binary search finds.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function lengthOfLIS(nums: number[]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n log n)
Space: O(n)
Solution 1 - O(n²) DP
Good baseline because it makes the recurrence very clear.
export function lengthOfLIS(nums: number[]): number {
if (nums.length === 0) {
return 0
}
const dp = new Array(nums.length).fill(1)
let best = 1
for (let index = 0; index < nums.length; index += 1) {
for (let previous = 0; previous < index; previous += 1) {
if (nums[previous] < nums[index]) {
dp[index] = Math.max(dp[index], dp[previous] + 1)
}
}
best = Math.max(best, dp[index])
}
return best
}It works well and teaches the rule.
But every position looks at all previous ones.
Solution 2 - tails plus binary search
Now the goal is not storing every answer by index.
It is storing the best possible ending for each length.
export function lengthOfLIS(nums: number[]): number {
const tails: number[] = []
for (const num of nums) {
let left = 0
let right = tails.length
while (left < right) {
const middle = Math.floor((left + right) / 2)
if (tails[middle] < num) {
left = middle + 1
} else {
right = middle
}
}
tails[left] = num
}
return tails.length
}The strong insight here is:
tailsis not necessarily the final subsequence- it is the best frontier for future growth
What to say in the interview
A strong short explanation would be:
The baseline uses DP:
dp[i]is the best increasing subsequence ending ati, so I test all smaller previous values. The stronger version replaces that with atailsarray, where each position stores the smallest possible ending for a given length. With binary search, I find where the current number improves that frontier and reachO(n log n).
That shows that you:
- understand the DP version first
- can explain why
tailsworks - do not sell binary search as a magic trick
When this pattern shows up again
This pattern comes back when you need to:
- think in subsequences instead of contiguity
- keep the best frontier for future growth
- combine dynamic programming with binary search
- optimize an O(n²) answer without losing the intuition
The point is not memorizing
tails.
The point is learning to ask which state leaves the most room to grow later.