Longest Increasing Subsequence

Medium

Problem

Return the length of the longest strictly increasing subsequence (not necessarily contiguous). The O(n log n) solution is the expected follow-up.

Example 1

Input:  [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

[2, 3, 7, 101].

Test cases

Case 1

Input:    [10,9,2,5,3,7,101,18]
Expected: 4

Case 2

Input:    [0,1,0,3,2,3]
Expected: 4

Case 3

Input:    [7,7,7,7]
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. DP O(n²)

Time O(n²)Space O(n)

dp[i] = longest increasing subsequence ending at i = 1 + max(dp[j]) for j<i with nums[j]<nums[i].

function lengthOfLIS(nums) {
const dp = Array(nums.length).fill(1);
let best = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++)
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return best;
}

2. Patience sorting + binary search

Time O(n log n)Space O(n)

Maintain `tails`, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. Binary-search the insert point.

function lengthOfLIS(nums) {
const tails = [];
for (const x of nums) {
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
tails[lo] = x;
}
return tails.length;
}