Q43: Longest Increasing Subsequence (LIS)
Find the length of the longest strictly increasing subsequence in an integer array.
Patience Sort Binary Search LIS O(n log n)
function lengthOfLIS(nums) {
const tails = [];
for (let num of nums) {
let left = 0;
let right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) left = mid + 1;
else right = mid;
}
tails[left] = num;
}
return tails.length;
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 ([2, 3, 7, 101])💡 Maintains array
tails storing smallest tail values of increasing subsequences. For each num, uses binary search to replace smallest element >= num or append num if larger than all tails.Key Takeaways
- Standard Dynamic Programming approach takes $O(n^2)$ time.
- Patience Sorting with Binary Search optimizes LIS execution to $O(n \log n)$ time.
Knowledge Check
What is the time complexity of the Patience Sorting Binary Search LIS algorithm?