Longest increasing subsequence
Find the longest list of items you can pick, in their original order, where each picked item is bigger than the one before.
O(n²)Space O(n)7 practice problemsStep-through pictureThe idea
A subsequence is what you get by deleting some items from a list without changing the order of the rest. From [3, 1, 4, 1, 5] you can get [3, 4, 5] or [1, 1, 5], but not [5, 4]. The items do not have to be next to each other.
The longest increasing subsequence, or LIS, is the longest subsequence where every item is strictly bigger than the one before it. For [8, 3, 6, 1, 4, 9, 7, 10] it has length 4, for example [3, 6, 7, 10].
The DP idea: let length[i] be the length of the longest increasing subsequence that ends exactly at item i. To find it, look at every earlier item j that is smaller than item i. You can put item i after the best subsequence ending at j.
An everyday example
Stacking boxes by height
Boxes come past you on a belt, one at a time, and you can pull some off to build a tower where every box is taller than the one under it. You can't change their order on the belt. For each new box, you ask: which towers that I could have built so far end with a shorter box? I could put this box on top of the tallest such tower.
| In the example | In the code |
|---|---|
| The boxes in order on the belt | The nums array |
| The best tower with this box on top | length[i] |
| A shorter earlier box this one can go on | nums[j] < nums[i] with j < i |
| Putting this box on that tower | length[j] + 1 |
| The tallest tower of all | Math.max(...length) |
From the slow way to longest increasing subsequence
- Start with brute force: list every subsequence, keep the ones that are strictly increasing, and return the longest length. A list of
nitems has2^nsubsequences, because each item is either kept or dropped. For 30 items that is 1,073,741,824 subsequences to check. - Think about how an increasing subsequence grows. To add an item to the end, you only need to know the last item so far, since the new item must be bigger. The items before the last one don't matter for the next choice. So the useful question is about the ending: "what's the longest increasing subsequence that ends at this item?"
- Call that
length[i]. An increasing subsequence ending at itemiis either itemialone, or a subsequence ending at some earlier itemjwithnums[j] < nums[i], followed by itemi. The best suchjgiveslength[j] + 1. So each cell comes from the cells to its left. - Fill
lengthfrom left to right: start every cell at 1, and for eachi, look at every earlierjand keep the largestlength[j] + 1among the smaller items. The longest overall can end anywhere, so the answer is the largest cell. That double loop is the LIS DP.
How it works
- Make
lengthwith one cell per item, all1: every item alone is an increasing subsequence of length 1. - For each item
ifrom left to right, look at every earlier itemj. - If
nums[j] < nums[i], itemican extend the subsequence that ends atj, giving lengthlength[j] + 1. - Keep the largest such value in
length[i]. - The answer is the largest value anywhere in
length, because the longest subsequence can end at any item.
Watch it run
This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.
See every step at onceThe same run, laid out side by side
The code
Point at a note to light up the lines it explains.
function longestIncreasing(nums) {if (nums.length === 0) return 0;const length = new Array(nums.length).fill(1);for (let i = 1; i < nums.length; i++) {for (let j = 0; j < i; j++) {if (nums[j] < nums[i]) {length[i] = Math.max(length[i], length[j] + 1);}}}return Math.max(...length);}
How fast it is
| Time | O(n²) |
|---|---|
| Extra memory | O(n) |
Each of the n items compares itself with every earlier item. The table has one number per item. The binary search version brings the time down to O(n log n).
- Best case
O(n²)Any list, even one already in increasing order: the inner loop still checks every earlier item for every
i. - Average case
O(n²)Any list: about
n × (n - 1) / 2comparisons, which is 499,500 for 1,000 items. - Worst case
O(n²)The same count. The values change which cells update, not how many comparisons are made.
Common mistakes
- Returning
length[n - 1]instead of the largest cell. The longest subsequence doesn't have to end at the last item. - Using
<=when the question says strictly increasing, or<when equal items are allowed. Read the rule carefully. - Confusing a subsequence (items may be skipped) with a subarray (items must be next to each other). The longest run of neighbors is a different, simpler problem.
- Calling
Math.max(...length)on a very large array, which can exceed the engine's argument limit. Track the maximum in a variable for big inputs.
When to use it
Look for these clues in a problem:
- The question asks for the longest chain of items in order where each one is bigger, later, or fits inside the next.
- Items can be skipped, but their order can't change.
- Pairs like (width, height) must both increase, which becomes LIS after sorting by one of them.
- The question asks for the fewest items to delete so the rest is sorted: that is the length minus the LIS.
Check yourself
Answer each one in your head first, then open it.
Why does every cell start at 1?
Any single item is an increasing subsequence by itself, so the longest one ending at that item has length at least 1.
Why is the answer the largest cell and not length[n - 1]?
The longest subsequence can end at any item. For [1, 3, 5, 2], length[3] is 2, but the answer is 3, ending at 5.
In the trace, why does 5 get length 3 but 4 only gets 2?
4 can only follow 2, which has length 1. 5 can follow 4, which has length 2, so 5 extends the subsequence 2, 4 to length 3.
How many comparisons does the inner loop make for 7 items?
21, which is 7 × 6 / 2: 1 for i = 1, 2 for i = 2, and so on up to 6 for i = 6.
Practice problems
Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.
0 of 7 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.
Start practicingGo further
You don't need these to start practicing. Open one when you want more.
Why it works
The reasoning that makes it always right
The table keeps one promise: after the outer loop handles i, length[i] is the length of the longest strictly increasing subsequence that ends exactly at nums[i]. Item 0 has nothing before it, so length[0] = 1 is right from the start.
Each pass keeps the promise. Take a longest increasing subsequence ending at i. If it has only one item, its length is 1, the starting value. Otherwise remove its last item: what's left is an increasing subsequence ending at some j < i with nums[j] < nums[i], and it can be no longer than length[j]. So the true answer is at most length[j] + 1 for some valid j, and every such value is reachable by putting nums[i] after the best subsequence ending at j. The inner loop checks every j, so it finds the maximum.
The order makes the reads safe: length[j] for every j < i is final before pass i begins. Every increasing subsequence ends at some item, so the longest one overall is the largest cell, which is what line 11 returns.
Going deeper
3 more ideas
What each cell means
length[i] is the length of the longest strictly increasing subsequence whose last item is nums[i]. Fixing the last item is what makes the transition easy: anything placed before it must be smaller and earlier.
How much work it does
Each item looks at every earlier item, so about n * n / 2 comparisons: O(n^2) time and O(n) space. That is fine for a few thousand items.
A faster version in O(n log n)
Keep an array tails, where tails[k] is the smallest possible last item of an increasing subsequence of length k + 1. For each number, binary search for the first tail that is greater than or equal to it and replace that tail, or append the number if it is bigger than every tail. The final length of tails is the LIS length. tails itself is not always a real subsequence, only its length is right.
Work it by hand
Every step in a table, with why
Find the length of the longest strictly increasing subsequence of 7 numbers. Each row is one pass of the outer loop.
nums = [6, 2, 8, 4, 5, 1, 7]
| Step | i | nums[i] | Smaller earlier items | length[i] | length after | What happens | Why |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 6 | - | 1 | 1, 1, 1, 1, 1, 1, 1 | Every cell starts at 1 | Line 3: each item alone is an increasing subsequence of length 1. The outer loop starts at i = 1. |
| 2 | 1 | 2 | none | 1 | 1, 1, 1, 1, 1, 1, 1 | Nothing to extend | 6 is bigger than 2, so 2 can't come after it. length[1] stays 1. |
| 3 | 2 | 8 | 6, 2 | 2 | 1, 1, 2, 1, 1, 1, 1 | Extends 6 or 2 | Both earlier items are smaller, and both have length 1, so 8 gets 1 + 1 = 2. |
| 4 | 3 | 4 | 2 | 2 | 1, 1, 2, 2, 1, 1, 1 | Extends 2 | 6 and 8 are bigger, so only 2 can come before 4. |
| 5 | 4 | 5 | 2, 4 | 3 | 1, 1, 2, 2, 3, 1, 1 | Extends 4: 2 + 1 | Extending 2 gives 2, extending 4 gives 3. Math.max keeps 3: the subsequence 2, 4, 5. |
| 6 | 5 | 1 | none | 1 | 1, 1, 2, 2, 3, 1, 1 | Smallest so far | Nothing earlier is smaller than 1. |
| 7 | 6 | 7 | 6, 2, 4, 5, 1 | 4 | 1, 1, 2, 2, 3, 1, 4 | Extends 5: 3 + 1 | Five earlier items are smaller. The best is 5 with length 3, so 7 gets 4. The loop ends and line 11 takes the largest cell. |
It returns 4, for the subsequence 2, 4, 5, 7. The answer here happens to end at the last item, but the code takes the largest cell anywhere, since that isn't true in general.
Compared with other ways
When to pick something else
| Approach | Time | Extra memory | Choose it when |
|---|---|---|---|
| Longest increasing subsequence | O(n²) | O(n) | Up to a few thousand items, or when you need the variants that count or rebuild sequences, which are easiest on this table. |
Binary search with tails | O(n log n) | O(n) | Long lists, such as 100,000 items or more, when the length is what matters. |
| LCS with a sorted copy | O(n²) | O(n²) | Rarely: the LIS equals the LCS of the list and its sorted copy without duplicates, but it uses more memory for no gain. |
| Try every subsequence | O(2^n) | O(n) | Only to check answers on lists of 15 items or fewer. |
Extra memory: O(n) for the length array, one number per item.
How the steps grow
- Longest increasing subsequence, LCS with a sorted copy
O(n²) - Binary search with
tailsO(n log n) - Try every subsequence
O(2^n)
| Approach | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| Longest increasing subsequence | 100 | 1 million | 1 trillion |
Binary search with tails | 33 | 9,966 | 20 million |
| LCS with a sorted copy | 100 | 1 million | 1 trillion |
| Try every subsequence | 1,024 | more than a quadrillion | more than a quadrillion |
Inputs that need care
5 tricky inputs
- An empty list:
nums = [] - Line 2 returns 0. Without that check,
Math.max()with no arguments would return-Infinity. - One item:
nums = [42] - The outer loop never runs, and the largest cell is 1.
- All equal:
nums = [3, 3, 3] 3 < 3is false, so no item extends another, and it returns 1. If the rule were "never decreasing", use<=and the answer becomes 3.- Strictly decreasing:
nums = [9, 7, 4] - No earlier item is smaller, so every cell stays 1 and it returns 1.
- A list of 200,000 items
- That is about 20 billion comparisons, far too slow, and
Math.max(...length)can pass the engine's argument limit. Use theO(n log n)version, and track the maximum in a variable.
Variations and follow-ups
Twists interviewers add
The O(n log n) version with tails
Keep tails[k], the smallest last item of any increasing subsequence of length k + 1. tails is always sorted, so each number binary searches for the first tail that is at least as big and replaces it, or adds itself at the end. For this trace's input, tails ends as [1, 4, 5, 7]: the right length, but not a real subsequence, since 1 comes after 5 in the list.
Rebuilding the subsequence
Keep prev[i], the j that gave length[i] its value. Start from the index of the largest cell and follow prev back, then reverse the list. For the trace, that walks 7, 5, 4, 2.
Counting the longest ones
Keep a second array count[i]: how many longest subsequences end at i. When length[j] + 1 beats length[i], copy count[j]; when it ties, add count[j]. Sum count over the cells with the largest length.
Chains of pairs and nested boxes
Many problems hide an LIS. To nest envelopes by width and height, sort by width, break ties by height from largest to smallest, and find the LIS of the heights. The sort turns a 2-D question into a 1-D one.
In an interview
Spot it, explain it, answer follow-ups
- Spot it from "keep the original order" plus "increasing", "chain", "nest", or "stack on top of each other". If items must be next to each other, it's a subarray problem instead.
- Say the state with the word "ends": "
length[i]is the longest increasing subsequence that ends exactly ati". Then explain why the answer is the largest cell, not the last one. - Test it on a list where the best subsequence doesn't end at the last item, such as
[1, 3, 5, 2], which should give 3. Also try all-equal and decreasing lists. - Expect "can you do better than
O(n²)?". Describetailsand its binary search, and warn thattailsitself isn't the subsequence; only its length is the answer.
Where frontend code uses it
The same idea in real UI code
- When a list of keyed children is reordered, Vue 3's renderer finds the longest increasing subsequence of the old positions; those nodes stay put and only the others are moved in the DOM.
- Sorting a playlist or kanban column with the fewest drag-and-drop moves keeps the LIS in place and moves everything else.
- Nesting cards or modals, where each must be both narrower and shorter than the one around it, is LIS on pairs after sorting.