LeetCode-in-All

300. Longest Increasing Subsequence

Medium

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]

Output: 1

Constraints:

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Solution

function lengthOfLIS(nums: number[]): number {
    if (nums === null || nums.length === 0) {
        return 0
    }
    const dp: number[] = new Array(nums.length + 1).fill(0)
    // Prefill the dp table
    for (let i = 1; i < dp.length; i++) {
        dp[i] = Number.MAX_SAFE_INTEGER
    }
    let left: number = 1
    let right: number = 1
    for (const curr of nums) {
        let start: number = left
        let end: number = right
        // Binary search, find the one that is lower than curr
        while (start + 1 < end) {
            let mid: number = start + Math.floor((end - start) / 2)
            if (dp[mid] > curr) {
                end = mid
            } else {
                start = mid
            }
        }
        // Update our dp table
        if (dp[start] > curr) {
            dp[start] = curr
        } else if (curr > dp[start] && curr < dp[end]) {
            dp[end] = curr
        } else if (curr > dp[end]) {
            dp[++end] = curr
            right++
        }
    }
    return right
}

export { lengthOfLIS }