Longest Increasing Subsequence
Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence can delete zero or more elements without changing the order of the remaining elements.
Input
An integer array nums.
Output
An integer: the length of the longest strictly increasing subsequence.
Constraints
- •
1 <= nums.length <= 2500 - •
-10^4 <= nums[i] <= 10^4
Examples
Example 1
nums = [10,9,2,5,3,7,101,18]
4Example 2
nums = [0,1,0,3,2,3]
4Example 3
nums = [7,7,7,7,7,7,7]
1Learning Objectives
- Define a sequence DP state by asking what the best subsequence ending at each index looks like.
- Distinguish subsequences from subarrays: order is preserved, contiguity is not required.
- Use binary search over minimal tail values to improve LIS from O(n^2) to O(n log n).
- Explain why the patience-sorting tails array stores lengths, not the exact final subsequence.
Intuition
The key question is not just which numbers are in the subsequence; it is where the subsequence ends. If nums[i] is the final value, then every previous value smaller than nums[i] is a possible predecessor. The best subsequence ending at i is one longer than the best predecessor among those candidates.
That gives the classic quadratic DP. For interviews, it is the safest recurrence to derive because every transition has a clear meaning.
The faster idea keeps a different summary. For every possible length, store the smallest tail value seen so far. A smaller tail is always better because it leaves more room for future numbers to extend the subsequence. When a new number arrives, binary search the first tail that is at least that number and replace it. Replacing does not claim the exact subsequence exists with those tail values all together; it preserves the best extension opportunity for each length.
Common mistakes
- ×Treating the answer as a longest increasing subarray and requiring contiguous elements.
- ×Using <= instead of <, which accidentally allows equal values in a strictly increasing subsequence.
- ×For the O(n^2) DP, defining **dp[i]** as a global answer so far instead of a subsequence that must end at **i**.
- ×For patience sorting, thinking the **tails** array is always the actual LIS rather than a compact set of best tail candidates.
- ×Returning **tails[0]** or a tail value instead of the number of occupied tail slots.
State Definition
For the quadratic DP, let dp[i] be the length of the longest strictly increasing subsequence that ends exactly at index i. The answer is max(dp[i]) over all indices.
For the binary-search solution, let tails[length - 1] be the smallest possible tail value of any increasing subsequence of length length seen so far. The number of filled entries in tails is the current LIS length.
State Transition
Quadratic recurrence:
dp[i] = 1 + max(dp[j]) over all j < i where nums[j] < nums[i]. If no such j exists, dp[i] = 1 because nums[i] alone is a subsequence.
Patience-sorting transition:
For each value x, binary search the first position pos where tails[pos] >= x. Set tails[pos] = x. If pos equals the current filled size, extend the size by one.
The base state is empty before scanning any number. In the DP form, each dp[i] starts at 1.
Solutions
Solution 1: Quadratic DP by ending index
Use this when you need the most explainable LIS recurrence, when n is only a few thousand, or when a follow-up asks you to reconstruct the subsequence with parent pointers. It is the canonical teaching solution before the O(n log n) optimization.
Process indices from left to right. For each i, scan every earlier j and extend only those subsequences whose tail value is smaller than nums[i]. Keep the best length that ends at i, then update the global answer.
Step-by-step
- Create an array dp of length n.
- For every index i, initialise dp[i] = 1 because a single element is always an increasing subsequence.
- Scan all j < i. If nums[j] < nums[i], candidate length dp[j] + 1 can end at i.
- Store the best candidate in dp[i] and update the answer with dp[i].
O(n^2)
O(n)
Every ordered pair of indices is considered once, and the DP array stores one value per index.
Java implementation
Solution 2: Patience sorting with binary search
Use this when the interviewer asks for the best asymptotic LIS length algorithm or when n is large. It is less direct for reconstruction, but it is the expected optimized solution for LeetCode 300.
Maintain tails, where each slot represents the smallest possible ending value for a subsequence of that length. A new number either extends all known lengths or improves the tail for one existing length. Binary search finds exactly which slot should change.
Step-by-step
- Start with an empty tails array and size = 0.
- For each number, binary search the first index whose tail is greater than or equal to that number.
- Replace that tail with the number. This keeps the tail as small as possible for that subsequence length.
- If the replacement happened just after the current last filled slot, increase size.
- Return size, the number of subsequence lengths currently represented.
O(n log n)
O(n)
Each of the n numbers performs one binary search over the current tail list.
Java implementation
Dry Run
Sample input
nums = [10,9,2,5,3,7,101,18]. Trace the optimized tails representation after each number.
| num | binary-search position | tails after update | current LIS length |
|---|---|---|---|
| 10 | 0 | [10] | 1 |
| 9 | 0 | [9] | 1 |
| 2 | 0 | [2] | 1 |
| 5 | 1 | [2,5] | 2 |
| 3 | 1 | [2,3] | 2 |
| 7 | 2 | [2,3,7] | 3 |
| 101 | 3 | [2,3,7,101] | 4 |
| 18 | 3 | [2,3,7,18] | 4 |
The final length is 4. The last tails array is not necessarily the chosen subsequence from the input; it is the best set of tail values for lengths 1 through 4.
Complexity Analysis
The O(n^2) DP is the clearest recurrence and is acceptable for small constraints. The patience-sorting solution is the optimized length-only algorithm at O(n log n).
Quadratic DP by ending index
O(n^2)
O(n)
Every ordered pair of indices is considered once, and the DP array stores one value per index.
Patience sorting with binary search
O(n log n)
O(n)
Each of the n numbers performs one binary search over the current tail list.
Interview Tips
Derive the O(n^2) DP first because it proves you understand the subsequence dependency. Then say that the only information needed for extension is the smallest tail for each length, which motivates binary search. Be explicit that strict increasing means the binary search replaces the first tail greater than or equal to the current number.
Likely follow-ups
- How would you reconstruct one actual LIS instead of only its length?
- How does the binary search change if the subsequence can be non-decreasing?
- How would you count the number of longest increasing subsequences?
- How would you solve the 2D version, Russian Doll Envelopes?
Similar Problems
Key Takeaways
- A subsequence DP often needs a state tied to the ending index.
- For LIS, **dp[i]** means the best increasing subsequence that must end at **i**.
- The O(n log n) solution keeps minimal tails, not the exact subsequence.
- Strictness matters: equal values should replace a tail, not extend the length.