Longest Increasing Subsequence
On this page
Problem statement
Given a list of integers, return the length of its longest strictly increasing subsequence. A subsequence keeps the original order but may skip any elements; it does not need to be contiguous.
This one is asked for two reasons: the O(n²) DP is a clean first DP, and the O(n log n) "tails + binary search" version separates good answers from strong ones. Original problem: LeetCode 300.
Example

Input: [3, 1, 8, 2, 5, 9, 4, 7]
Output: 4 # e.g. 1, 2, 5, 7
Input: [5, 5, 5]
Output: 1 # strictly increasing, so equal values don't chain
Constraints (assumed)
- 1 ≤ n ≤ 2,500 (enough for O(n²); the follow-up asks for O(n log n)).
- −10⁴ ≤ value ≤ 10⁴.
What this question tests
- Defining a DP state that ends at index i, which is what makes the recurrence simple.
- Knowing (and explaining) the patience-sorting / tails improvement to O(n log n).
- Getting strict vs non-strict right in the binary search.
Questions to ask first
- Strictly increasing or non-decreasing? (Here: strict.) This decides
bisect_leftvsbisect_right. - Length only, or the subsequence itself? Rebuilding it needs extra bookkeeping.
- How large is n? O(n²) is fine for a few thousand, not for a million.
- Empty input? Return 0.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.