LeetCode 300 ·
Medium
Longest Increasing Subsequence
Find the length of the longest strictly increasing subsequence.
Try it
Step through the core mechanic. The simulator below runs the dynamic programming shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Dynamic programming — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
O(n²) DP: dp[i] = 1 + max dp[j] for j<i with nums[j]<nums[i]. The O(n log n) version keeps a "tails" array and binary-searches the insertion point for each value.
| Aspect | Value |
|---|---|
| Pattern | Dynamic programming |
| Recognise it by | Longest strictly increasing subsequence. |
| Time complexity | O(n log n) |
| Space complexity | O(n) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.