#300
Longest Increasing Subsequence
Medium Patience sorting + binary search
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the length of the longest strictly increasing subsequence.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest strictly increasing subsequence.
Why this works: tails[k] = the smallest possible tail of an increasing run of length k + 1. Each number replaces the first tail ≥ it (binary search).
Example: [10, 9, 2, 5, 3, 7, 101, 18]
tails: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]length 4
✦Hints open one at a time
O(n²) DP: dp[i] = 1 + max dp[j] for j < i with nums[j] < nums[i].
Faster: tails[k] = the smallest possible tail of an increasing subsequence of length k + 1.
For each number, binary search the first tail >= it and replace it (or append).
↗Approach
Maintain the sorted tails array. Each number either extends the longest subsequence or improves (lowers) some tail. The array's length is the answer.
</>Solution (Java)
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int len = 0;
for (int x : nums) {
int lo = 0, hi = len;
while (lo < hi) { // first tail >= x
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) lo = mid + 1;
else hi = mid;
}
tails[lo] = x;
if (lo == len) len++; // extended the longest one
}
return len;
}
}!Common mistake
Thinking tails is an actual LIS — only its length is meaningful.
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Dynamic Programming
🎬 Episodes 86–96: video coming soon