262. Longest Increasing Subsequence
Your function receives an integer array nums and must return one integer: the length of the longest strictly increasing subsequence hiding inside it.
A subsequence is what remains after deleting zero or more elements without disturbing the order of the rest — the kept elements need not be adjacent. Strictly increasing means every kept element is larger than the one before it, so equal values never extend a chain ([3, 3] counts as length 1).
The classic dynamic program solves this in O(n²). Can you get to O(n log n)?
Example 1:
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: One best pick is 2, 3, 7, 18 (2, 5, 7, 101 works too) — four elements in order, each larger than the last. No five-element increasing chain exists.
Example 2:
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: Take 0, 1, 2, 3 (positions 1, 2, 5, 6). The repeated values can only be used once each, since the chain must strictly grow.
Example 3:
Input: nums = [7, 7, 7, 7]
Output: 1
Explanation: Every element equals every other, and equal values do not count as increasing, so no chain is longer than a single element.
Constraints:
- 1 ≤ nums.length ≤ 2500
- -10⁴ ≤ nums[i] ≤ 10⁴
Hints:
Define dp[i] as the length of the longest increasing chain that ends exactly at index i. Then dp[i] = 1 + the best dp[j] over all j < i with nums[j] < nums[i] — an O(n²) double loop.
For O(n log n), maintain an array tails where tails[k] is the smallest possible last value of any increasing chain of length k+1. Each new number either extends tails (it beats every entry) or lowers the first entry that is >= it — found by binary search. The array stays sorted; its final length is the answer.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Expected output: 4