DSA problem
Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived from the array by deleting zero or more elements without changing the order of the remaining elements.
The most intuitive solution is the classic dynamic programming formulation: let dp[i] denote the length of the longest increasing subsequence ending at index i. For every j < i with nums[j] < nums[i], you can extend that subsequence by one, giving dp[i] = max(dp[i], dp[j] + 1). The answer is max(dp). This runs in O(n²) time and O(n) space and is acceptable for moderate inputs.
For larger inputs the standard accelerated approach is a patience-sort variant powered by binary search. Maintain an array tails where tails[k] holds the smallest possible tail value of any increasing subsequence of length k + 1 seen so far. The crucial invariant is that tails itself is strictly increasing, which makes binary search applicable.
For each new number x, binary search for the leftmost index i in tails such that tails[i] >= x. If i equals the length of tails, append x (we just extended the longest known subsequence). Otherwise replace tails[i] with x (we found a subsequence of the same length but with a smaller tail, leaving more room to grow). The final answer is the length of tails. The whole algorithm runs in O(n log n) time and O(n) space. Note that tails is not itself a valid LIS — it only encodes the correct length.
Examples
nums = [10,9,2,5,3,7,101,18]4nums = [0,1,0,3,2,3]4nums = [7,7,7,7,7,7,7]1Constraints
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 10^4
- The subsequence must be strictly increasing (equal values do not count).
- Aim for O(n log n) time using the patience-sort + binary search technique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.