Longest Increasing Subsequence
Understand the problem
Given an integer array nums. Find the length of the longest strictly increasing subsequence. The subsequence does not have to be contiguous.
Examples:
ts
nums = [10, 9, 2, 5, 3, 7, 101, 18]
output = 4 // subsequence: [2, 3, 7, 101] or [2, 5, 7, 101]
nums = [0, 1, 0, 3, 2, 3]
output = 4 // subsequence: [0, 1, 2, 3]
nums = [7, 7, 7, 7]
output = 1 // just 1 element (strictly increasing, no two equal elements)Key point: a "subsequence" is different from a "subarray" (contiguous) — you may skip elements in between.
Basic approach
O(n²) time, O(n) spacets
// DP O(n²) — the classic, good enough for interviews
function lengthOfLIS(nums: number[]): number {
const n = nums.length
if (n === 0) return 0 // empty array → LIS = 0 (avoids Math.max(...[]) = -Infinity)
// dp[i] = length of the LIS ending at index i
const dp = new Array(n).fill(1)
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
// nums[i] can extend the subsequence ending at nums[j]
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
}
return Math.max(...dp)
}Why this approach is slow:
For each index i, look at every j < i to find a smaller element that can come before it.
Good enough for n ≤ 2500, but for n = 10⁵ you need O(n log n).
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.