Longest Increasing Subsequence
Problem statement
Given a list of integers nums, return the length of the longest strictly increasing subsequence.
A subsequence keeps the original order but may skip elements; it does not have to be contiguous. Strictly increasing means each chosen value is larger than the one before it, so equal values can't both be used.
Examples
Example 1
Input: nums = [3,1,8,2,5,9]
Output: 4
Explanation: 1, 2, 5, 9 is one longest choice. 3, 8, 9 is increasing too, but shorter.
Example 2
Input: nums = [7,7,7]
Output: 1
Explanation: Equal values don't count as increasing, so only one can be used.
Hints
Approach
Patience sorting with binary search. Keep a list tails, where tails[k] is the smallest last value of any increasing subsequence of length k + 1 seen so far. tails is always sorted.
For each x, binary search for the first entry >= x. If there is none, x extends the longest subsequence: append it. Otherwise replace that entry with x, since a smaller tail for the same length can only help later elements. The final length of tails is the answer.
tails is not itself a valid subsequence; only its length is meaningful. Searching for >= x (lower bound) rather than > x is what enforces strictly increasing.
O(n log n)Space O(n)from bisect import bisect_left def length_of_lis(nums): tails = [] for x in nums: i = bisect_left(tails, x) if i == len(tails): tails.append(x) else: tails[i] = x return len(tails) print(length_of_lis([3, 1, 8, 2, 5, 9]))print(length_of_lis([7, 7, 7]))Follow-up questions
- Return one actual longest subsequence, not just its length.
- Count how many different longest increasing subsequences exist (Number of Longest Increasing Subsequence).
Frequently asked questions
It is one of the core DP problems in SWE-style loops, and it is often used to see whether a candidate can go past the obvious O(n²) DP. A practical echo: finding the longest run of versions or timestamps that are already in order, which tells you how few items must move to sort the rest.
Each tails[k] records the best possible ending for length k + 1, but different entries may come from different subsequences. The algorithm only promises that a subsequence of length len(tails) exists. To recover one, store a predecessor index for each element as you go.
Use an upper-bound search (bisect_right, first entry > x) so equal values extend the subsequence instead of replacing an equal tail.