# Longest Increasing Subsequence > Find the length of the longest strictly increasing subsequence. Keep the smallest possible tail for every length, and binary search that sorted list to place each number. - Track: DSA (Dynamic Programming) - Level: Medium - Format: Step-through player - Author: Aayush Ostwal - Published: 25 October 2026 - Topics: Dynamic programming, Binary search - LeetCode: https://leetcode.com/problems/longest-increasing-subsequence/ - Canonical URL: https://compoundengineer.com/library/dsa/longest-increasing-subsequence Dynamic programming · Patience sorting (tails + binary search) Medium · O(n log n) time · O(n) space ## Problem Given an integer array nums , return the length of the longest strictly increasing subsequence . A subsequence keeps the original order but may skip elements. Example 1 Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 (for example 2, 3, 7, 18) Example 2 Input: nums = [7, 7, 7, 7] Output: 1 (equal values do not count as increasing) Constraints 1 ≤ nums.length ≤ 2500 −10^4 ≤ nums[i] ≤ 10^4 ## Brute force Imagine a row of numbers. You may cross out as many as you like, but you may not move the rest. What is the longest run you can keep where every number is bigger than the one before it ? That kept run is a subsequence . - Keep the original order. You may skip numbers, but never swap them. - Each kept number must be strictly bigger than the previous one, so equal numbers do not count. - Return the length of the longest such run. The direct idea: for every number, choose to keep it or skip it, and see which choices give the longest run. ### The problem with it Each number has two choices, so n numbers give 2 n possibilities. With 2,500 numbers that is hopeless. ## How to think your way to the optimal solution The brute force asks the same small question over and over: "what is the longest run that ends at this number?" Let us answer it once per number. If we know the best run ending at every earlier number, how do we get it for the next one? Look at the earlier numbers that are smaller than the new one. The new number can be added to any of their runs. So its best run is one more than the best of those. This is the first, simpler solution. ## The optimal solution ### Approach 1: a table of runs The idea. Let dp[i] be the longest run that ends exactly at index i . For each i , look at every j before it. If nums[j] < nums[i] , the number at i can extend that run. - Start every dp[i] at 1: a number alone is a run of length 1. - For each i, check every earlier j. nums[j] Cost. For each number we look at all the numbers before it, so this takes O(n²) time and O(n) space. For 2,500 numbers that is fine. It is also a fair answer to give first in an interview. But we can do better. ### Approach 2: tails and binary search The idea. The table keeps far more than we need. Here is a smarter thing to keep. For each run length k , remember only the smallest number that a run of length k can end with . We call this list tails . A small tail is good, because a smaller number is easier to extend. The list is always sorted. A run of length 3 can always be shortened to a run of length 2 that ends with a smaller number, so the tails never go down as k grows. Because the list is sorted, we can find a place in it with binary search: guess the middle, and the answer ("too small" or "not too small") tells us which half to keep. What happens to each new number x : find the first tail that is not smaller than x . - Every tail is smaller than x. x is bigger than all of them⟶add x at the end: the longest run grew by one - Some tail is not smaller than x. found it at position k⟶replace it with x: a run of that length can now end lower, and the length does not change - The number of tails at the end is the answer. By hand , on [10, 9, 2, 5, 3, 7, 101, 18] : - 10. The list is empty, so add it: [10]. - 9. The first tail not smaller than 9 is 10. Replace it: [9]. - 2. Replace 9: [2]. - 5. 5 is bigger than 2, so add it: [2, 5]. The longest run is now 2. - 3. The first tail not smaller than 3 is 5. Replace it: [2, 3]. - 7. Bigger than all, so add it: [2, 3, 7]. - 101. Add it: [2, 3, 7, 101]. - 18. The first tail not smaller than 18 is 101. Replace it: [2, 3, 7, 18]. There are 4 tails, so the answer is 4 . Press Play to watch it. The player also has an input of four equal numbers, [7, 7, 7, 7] , so you can watch where equal numbers go: they replace a tail, and they never add. Cost. Each number does one binary search, which takes about log n steps, so the total is O(n log n). ## Complexity analysis | Approach | Time | Space | | --- | --- | --- | | Try every subsequence | 2n | O(n) | | --- | --- | --- | | A table of runs | O(n²) | O(n) | | --- | --- | --- | | Tails with binary search | O(n log n) | O(n) | | --- | --- | --- | O(n log n) Time. Here's why: there are n numbers. Each one does one binary search on the tails list, which is at most n long, so it takes about log n steps. The add or replace afterwards is one step. O(n) Space. The tails list never holds more than n numbers. Nothing else grows. ## Interviewer follow-ups These are the questions that usually come next. Open one to see an answer you could say out loud. "Return the actual subsequence, not just its length." What they are checking Whether you know that the tails list is not itself an answer. A common mistake is to print it. A strong answer The tails list has the right length, but it can mix numbers from different runs, so it is not always a real subsequence. For example, on [2, 5, 1] the tails become [1, 5] , but the 1 comes after the 5 in the array. To get a real one, I remember for each placed number the index of the tail just before it (its "previous" pointer), and also which index sits in each tail slot. At the end I start from the last slot and follow the pointers backwards. "Now equal numbers are allowed: find the longest non-decreasing run." What they are checking Whether you know exactly which line decides "strictly" and can change it with confidence. A strong answer One comparison changes. Now a tail that is equal to x can still be extended by x , so I look for the first tail that is bigger than x , not "not smaller". In code, tails[mid] < x becomes tails[mid] <= x (in Python, bisect_right instead of bisect_left ). On [7, 7, 7, 7] the answer changes from 1 to 4. "Why is it safe to replace a tail? You are throwing information away." What they are checking Whether you understand why the trick is correct, or only memorised it. A strong answer Replacing a tail with a smaller number never hurts. A run of that length that ends lower can be extended by every number that the old run could extend, and by more. The old, larger tail has no future that the new one lacks. And we do not lose the length: the length of the list only grows when a number is bigger than every tail, which is exactly when a longer run exists. ## Spot this pattern - You want the longest run of picks in order, where each pick must beat the one before it. - A table of "best run ending here" works in O(n²), and you are asked for faster. - Keeping the smallest possible ending for each length leaves a sorted list that you can binary search. ## Solution code ### Python ```python class Solution: def lengthOfLIS(self, nums): tails = [] # tails[k] = smallest last value of any increasing run of length k + 1 for x in nums: lo, hi = 0, len(tails) while lo < hi: mid = (lo + hi) // 2 if tails[mid] < x: lo = mid + 1 # x is too big to replace tails[mid] else: hi = mid # tails[mid] could be replaced by the smaller x if lo == len(tails): tails.append(x) # x extends the longest run else: tails[lo] = x # same length, smaller tail: never worse return len(tails) ``` ### Java ```java class Solution { public int lengthOfLIS(int[] nums) { List tails = new ArrayList<>(); // tails[k] = smallest last value of any increasing run of length k + 1 for (int x : nums) { int lo = 0, hi = tails.size(); while (lo < hi) { int mid = (lo + hi) / 2; if (tails.get(mid) < x) { lo = mid + 1; // x is too big to replace tails[mid] } else { hi = mid; // tails[mid] could be replaced by the smaller x } } if (lo == tails.size()) { tails.add(x); // x extends the longest run } else { tails.set(lo, x); // same length, smaller tail: never worse } } return tails.size(); } } ``` ### C++ ```cpp class Solution { public: int lengthOfLIS(vector& nums) { vector tails; // tails[k] = smallest last value of any increasing run of length k + 1 for (int x : nums) { int lo = 0, hi = tails.size(); while (lo < hi) { int mid = (lo + hi) / 2; if (tails[mid] < x) { lo = mid + 1; // x is too big to replace tails[mid] } else { hi = mid; // tails[mid] could be replaced by the smaller x } } if (lo == (int)tails.size()) { tails.push_back(x); // x extends the longest run } else { tails[lo] = x; // same length, smaller tail: never worse } } return tails.size(); } }; ``` --- From Compound Engineer (https://compoundengineer.com), visual lessons for engineers. The page above is the full interactive version.