leetcode-javascript/solutions/0300-longest-increasing-subsequence.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Longest Increasing Subsequence
 * Time Complexity: O(N log N)
 * Space Complexity: O(N)
 */
var lengthOfLIS = function (nums) {
    if (!nums || nums.length === 0) {
        return 0;
    }

    const increasingSubsequenceTails = [];

    for (const currentNumber of nums) {
        let binarySearchLeft = 0;
        let binarySearchRight = increasingSubsequenceTails.length - 1;
        let insertionPoint = increasingSubsequenceTails.length;

        while (binarySearchLeft <= binarySearchRight) {
            const binarySearchMid = Math.floor((binarySearchLeft + binarySearchRight) / 2);
            if (increasingSubsequenceTails[binarySearchMid] < currentNumber) {
                binarySearchLeft = binarySearchMid + 1;
            } else {
                insertionPoint = binarySearchMid;
                binarySearchRight = binarySearchMid - 1;
            }
        }

        if (insertionPoint === increasingSubsequenceTails.length) {
            increasingSubsequenceTails.push(currentNumber);
        } else {
            increasingSubsequenceTails[insertionPoint] = currentNumber;
        }
    }

    return increasingSubsequenceTails.length;
};