Intermediate LevelData Structures & Algorithms
How do you find the Longest Increasing Subsequence (LIS)?
ā Interview Prompt: Solve LIS using O(NĀ²) DP and the O(N log N) patience sorting / binary search approach.
O(NĀ²) DP:
dp[i] = LIS ending at index i.
dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i].
O(N log N) ā Patience Sorting / Binary Search:
Maintain a tails array where tails[i] = smallest tail element of all increasing subsequences of length i + 1.
ā¢
For each
num:ā¢
If
num > tails.last ā extend by 1 (append).ā¢
Else ā binary search for the leftmost tail ā„ num and replace it.
ā¢
LIS length =
tails.length.Code Implementation Example
typescript
// O(N log N) LIS via binary search on tails array
function lengthOfLIS(nums: number[]): number {
const tails: number[] = [];
for (const num of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) { // binary search: find first tail >= num
const mid = (lo + hi) >> 1;
if (tails[mid] < num) lo = mid + 1;
else hi = mid;
}
tails[lo] = num; // replace or extend
}
return tails.length;
}
console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4 ā [2,3,7,18]š”O(N log N) LIS using patience sorting and binary search on tails array.
šÆ Interview Key Takeaway
LIS has a classic O(NĀ²) DP and an elegant O(N log N) solution via binary search on a maintained tails array. Know both for interviews.
#DSA#LIS#Dynamic Programming#Binary Search#Intermediate
Back to all Data Structures & Algorithms Questionsā