The brute force way is to generate all possible subsequences of the array and check if they are strictly increasing. Since every element can either be included or excluded, there are 2^N possible subsequences. Generating them all and validating them takes O(N \cdot 2^N) time. For N=2500, 2^{2500} is an astronomically large number. We definitely need a polynomial time DP approach.
Subsequence, not subarray — gaps are allowed. That single word rules out sliding windows and rules in DP.
and dp[i] = 1 if no such j exists — the element alone.
The answer is the maximum over the whole table, not dp[n-1], because the best subsequence may end anywhere. That is the second most common mistake in this problem.
python
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [1] * len(nums) # (1) every element alone is length 1 for i in range(len(nums)): # (2) for j in range(i): # (3) if nums[j] < nums[i]: # (4) dp[i] = max(dp[i], dp[j] + 1) # (5) return max(dp) # (6)
O(n^2) time, O(n) space. Write this first. It is obviously correct and it is the answer if the follow-up never comes.
Line by line. Here dp[i] means "the length of the longest increasing subsequence that ends at nums[i]". (1) Every number on its own is an increasing subsequence of length 1. (2) For each position i, (3) look at every earlier position j. (4) If nums[j] is smaller, nums[i] can be added to the end of any increasing subsequence that ends at j. (5) That makes one of length dp[j] + 1, so keep the longest such option. (6) The longest subsequence can end anywhere, so the answer is the largest dp value. Two loops over n positions give O(n^2).
This one is worth real attention, because the array it maintains is not what people assume.
Keep an array tails, where tails[k] is the smallest possible value that can end an increasing subsequence of length k + 1, among everything seen so far.
For each new number, find the first entry in tails that is greater than or equal to it, and overwrite that entry. If no entry qualifies, append.
python
import bisectclass Solution: def lengthOfLIS(self, nums: List[int]) -> int: tails = [] # (7) for n in nums: # (8) i = bisect.bisect_left(tails, n) # (9) first index with tails[i] >= n if i == len(tails): # (10) tails.append(n) # extends the longest run else: tails[i] = n # (11) a smaller tail for that length return len(tails) # (12)
ts
function lengthOfLIS(nums: number[]): number { const tails: number[] = []; // (7) for (const n of nums) { // (8) let lo = 0, hi = tails.length; // (9) while (lo < hi) { // first index with tails[i] >= n const mid = (lo + hi) >> 1; if (tails[mid] < n) lo = mid + 1; else hi = mid; } if (lo === tails.length) tails.push(n); // (10) else tails[lo] = n; // (11) } return tails.length; // (12)}
(7) tails[k] is the smallest number that can end an increasing subsequence of length k + 1, using the numbers seen so far. It is not an actual subsequence. Its numbers can come from different subsequences. But it is always sorted from small to large, which is what lets us binary search it.
(8) Take each number in turn.
(9) Find the first entry in tails that is at least n.bisect_left is Python's built-in binary search for exactly this. TypeScript writes the same search by hand: shape B from 4.11.1. (lo + hi) >> 1 is a quick way to halve and round down.
(10) Every entry is smaller than n, so n can extend the longest subsequence so far. Add it at the end. The longest length grows by one.
(11) Otherwise, n replaces that entry. There is now a subsequence of that length ending in a smaller number, n. A smaller ending is better, because it leaves more room for later numbers to extend it.
(12) The number of entries is the length of the longest increasing subsequence.
tails is not the longest increasing subsequence. Its length is correct; its contents are usually not a real subsequence of the input. It is a set of best-possible endings, one per length. Do not return it as the answer to "give me the subsequence".
Why overwriting is safe. If you can end a length-3 subsequence with 7, and later you find you can end one with 5, then 5 is strictly better — every future number that could extend the 7 can also extend the 5, and some that could not extend 7 can extend 5. Keeping the smaller tail never loses an option.
Why tails stays sorted. A longer subsequence must end at a value at least as large as a shorter one's best ending, so the array is increasing by construction — which is what makes binary search legal.
bisect_left, not bisect_right.bisect_left finds the first entry ≥ n, so an equal value gets overwritten rather than appended, which is what "strictly increasing" requires. Switch to bisect_right and you get the longest non-decreasing subsequence — a one-word change in the problem, a one-function change in the code, and a good thing to point out.
Length 4 ✓. Note the final tails is [2,3,7,18], which is a valid subsequence here — but that is luck, not a guarantee.
O(n \log n) time, O(n) space.
Time Complexity Derivation: We loop through the N numbers exactly once. For each number, we do a binary search (bisect_left) over the tails array. The tails array has at most size N. Binary search on an array of size N takes O(\log N) time. So N iterations \timesO(\log N) work per iteration = O(N \log N) total time.
Space Complexity Derivation: We maintain a tails array which in the worst case (a completely strictly increasing array) will store all N elements. Thus, space is O(N).
Numbers that only go down. Each new number replaces the first entry, so tails stays length 1.
Repeated numbers, like [7, 7, 7]. "Increasing" means strictly bigger, so the answer is 1. Using bisect_left, which finds the first entry at leastn, makes an equal number replace rather than extend.
If asked for the subsequence rather than its length, keep for each element the index it was placed at in tails, plus a parent pointer to whatever was at the previous position when it was placed. Then walk the parents backwards from the last append.
Say that reconstruction needs extra bookkeeping, because it is the natural follow-up and a lot of people assume tails already is the answer.
Russian Doll Envelopes — sort by width ascending and by height descending within equal widths, then run LIS on the heights. The descending tie-break is what stops two envelopes of equal width being nested, and it is the whole trick.
Number of Longest Increasing Subsequences — count as well as measure, which needs a second table.
Longest Increasing Path in a Matrix — the grid version, solved with memoised DFS. 4.24.
Maximum Length of Pair Chain, Longest String Chain — sort first, then LIS.
The pattern to carry: "longest chain under some ordering" is LIS after a sort. Recognising it is what makes Russian Doll Envelopes a five-minute problem instead of a new one.
"What does dp[i] mean?" The longest increasing subsequence ending ati. The "ending at" is not optional.
"Why is the answer max(dp) and not dp[n-1]?" The best subsequence can end anywhere.
"What does tails hold?" The smallest possible tail for each length. Not an actual subsequence.
"Why is it safe to overwrite?" A smaller tail for the same length dominates a larger one — it can be extended by strictly more values.
"Why is tails sorted?" Longer subsequences need larger endings.
"Strictly increasing or non-decreasing?"bisect_left versus bisect_right.
"Can you return the subsequence itself?" Yes, with parent pointers.
One thing to volunteer: say clearly that tails is not the answer subsequence. It is the single most common misunderstanding of this algorithm, and correcting it unprompted shows you understand what the array is for.