Longest Increasing Subsequence
Problem statement
You are given a list of integers nums. Return the length of the longest strictly increasing subsequence.
A subsequence keeps some of the values in their original order and drops the rest; the kept values don't have to be next to each other. "Strictly increasing" means each kept value is bigger than the one before it — equal values don't count.
For example, in [3, 1, 4, 2, 5] you can keep 1, 2, 5 or 3, 4, 5, so the answer is 3.
Examples
Example 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: Keeping 2, 3, 7, 101 (or 2, 5, 7, 18) gives 4 values that rise each step. No choice of 5 values stays increasing.
Example 2
Input: nums = [0,1,0,3,2,3]
Output: 4
Explanation: 0, 1, 2, 3 uses the first 0, the 1, the 2 and the last 3, in that order. That is 4 values.
Example 3
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Explanation: Every value is the same, and equal values don't count as increasing, so only one 7 can be kept.
Hints
i, ask: what is the longest increasing subsequence that *ends* at nums[i]?Approach
Optimal: Smallest tails + binary search
Intuition
Keep a list called tails. Entry k holds the smallest last value of any increasing subsequence of length k + 1 found so far. Why the smallest? A subsequence that ends lower is easier to extend later — 2, 3 is more useful than 2, 5, because more future values are bigger than 3 than bigger than 5.
tails is always sorted, which makes each update cheap. For a new value x:
- If
xis bigger than every entry, it extends the longest subsequence: append it. - Otherwise, find the first entry that is
>= xand replace it withx. That keeps a subsequence of the same length but with a smaller ending.
The length of tails is the answer. Note that tails itself is usually not a real subsequence of nums — only its length is meaningful. Finding "the first entry >= x" is a binary search (look at the middle, keep the half that must contain it); using >= rather than > is what makes equal values not count as increasing.
Steps
- Start with an empty list
tails. - For each value
xinnums:- Binary-search for the first position
posintailswithtails[pos] >= x. - If
posequals the length oftails, appendx. Otherwise settails[pos] = x.
- Binary-search for the first position
- Return the length of
tails.
Dry run
nums = [10,9,2,5,3,7,101,18]
| x | first entry ≥ x | action | tails after |
|---|---|---|---|
| 10 | none | append | [10] |
| 9 | 10 | replace | [9] |
| 2 | 9 | replace | [2] |
| 5 | none | append | [2, 5] |
| 3 | 5 | replace | [2, 3] |
| 7 | none | append | [2, 3, 7] |
| 101 | none | append | [2, 3, 7, 101] |
| 18 | 101 | replace | [2, 3, 7, 18] |
The list has length 4. Edge case: [7,7,7] — each 7 finds the existing 7 (>= 7) and replaces it, so tails stays [7] and the answer is 1.
Complexity
Time O(n log n) - We handle each of the n values once. For each one, a binary search in the `tails` list finds where it goes, which takes O(log n) steps because the list is sorted and never longer than n. For n = 2,500 that is about 2,500 × 12 = 30,000 steps instead of 3 million.
Space O(n) - The `tails` list grows by at most one entry per value, so it holds at most n numbers. Nothing else is stored.
from bisect import bisect_left
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails: List[int] = []
for x in nums:
pos = bisect_left(tails, x) # first index with tails[pos] >= x
if pos == len(tails):
tails.append(x)
else:
tails[pos] = x
return len(tails)
if __name__ == "__main__":
print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])) # 4
print(Solution().lengthOfLIS([0, 1, 0, 3, 2, 3])) # 4
print(Solution().lengthOfLIS([7, 7, 7, 7, 7, 7, 7])) # 1RecapThe whole problem in a few lines, for the night before
- Spot it: longest strictly increasing subsequence, where elements need not be next to each other
- Idea: keep a
tailslist where tails[i] is the smallest possible last value of an increasing subsequence of length i + 1; for each number, binary search its position and replace it, or append if it is bigger than all; the answer is the list length - Cost: O(n log n) time, O(n) space (the simple DP is O(n²) time)
- Trap: use the lower-bound position so equal values replace instead of extending, since the sequence must be strictly increasing;
tailsis not the actual subsequence
Interview follow-ups
Return one longest increasing subsequence, not just its length.
With the O(n²) DP, also store
prev[i]: thejthat gavedp[i]its best value. Find theiwith the largestdp[i], then followprevback to the start and reverse the list. Time stays O(n²) and the extra array is O(n). The O(n log n) version can do it too with the predecessor trick from the FAQ.Count how many longest increasing subsequences there are.
Keep a second array
count[i]: the number of longest subsequences ending ati. Whendp[j] + 1 > dp[i], setdp[i] = dp[j] + 1andcount[i] = count[j]; when it's equal, addcount[j]tocount[i]. The answer is the sum ofcount[i]over alliwith the largestdp[i]. This stays O(n²).Values arrive one at a time and you must report the current answer after each one.
The
tailsapproach already works this way. Each new value does one binary search and one update, O(log n), and the current answer is just the length oftails. Memory is O(answer length), not O(n), because onlytailsis kept. The O(n²) DP would need to look back at every previous value for each new one.
Frequently asked questions
A subarray is a block of values that sit next to each other, like [2, 5, 3] inside [10, 9, 2, 5, 3, 7]. A subsequence may skip values but keeps their order, like [2, 3, 7]. This problem asks for a subsequence, which is why the answer can jump over values such as the 5.
Replacing an entry can mix values from different subsequences. For [3, 4, 1], tails ends as [1, 4], but 1 comes after 4 in the input, so [1, 4] isn't a real subsequence. The length is still right: there really is an increasing subsequence of length 2 (3, 4). Only the length is guaranteed.
Because the problem wants strictly increasing values. If x equals an entry, replacing that entry keeps the length the same, so equal values never make the list longer. Searching for the first value > x instead would append equal values and compute the longest non-decreasing subsequence — a different problem.
Yes, with a bit more bookkeeping. Store, for each position in tails, the index in nums of the value placed there, and for each value, the index of the value in the slot before it (its predecessor). At the end, start from the last slot and follow predecessors backward. Time stays O(n log n) and memory O(n).
It's a staple of software-engineering-heavy infra loops because it tests two things at once: turning a brute force into a DP, and then spotting a binary-search speed-up. The ordering idea also appears in real data, such as finding the longest run of monotonically increasing version numbers or sequence IDs in an out-of-order log.