Longest Increasing Subsequence

How it works

We maintain an array dp where dp[i] is the smallest ending element of all increasing subsequences of length i + 1. This array stays sorted. For each new element, if it's larger than the last element in dp, it extends the longest subsequence. Otherwise, we use binary search to find the position where it can replace an element, keeping the array optimal for future extensions.

Steps

1. Initialize dp with the first element.
2. For each subsequent element nums[i]:
   • If nums[i] is greater than dp[-1], append it to dp.
   • Otherwise, find the leftmost position in dp where dp[pos] >= nums[i] using binary search, and replace dp[pos] with nums[i].
3. The length of dp is the answer.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Confusing the Binary Search Array with the Actual LIS

In the binary search approach, the dp array at the end does not contain the actual longest increasing subsequence. It contains the smallest tail elements for subsequences of each length. The length of this array is the LIS length, but the elements themselves may not form a valid increasing subsequence from the original array.

Using Wrong Binary Search Condition

When finding the position to replace in the dp array, you need to find the leftmost position where dp[pos] >= nums[i]. Using > instead of >= can lead to duplicate values being treated as increasing, which violates the strictly increasing requirement.

Returning Wrong Value in Bottom-Up DP

In the O(n^2) DP approach, the answer is the maximum value across all dp[i], not just dp[n-1]. The longest increasing subsequence might end at any index, not necessarily the last one. Returning only the last element of the DP array misses cases where the LIS ends earlier in the array.

from typing import List

from bisect import bisect_left
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = []
        dp.append(nums[0])

        LIS = 1
        for i in range(1, len(nums)):
            if dp[-1] < nums[i]:
                dp.append(nums[i])
                LIS += 1
                continue

            idx = bisect_left(dp, nums[i])
            dp[idx] = nums[i]

        return LIS

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        dp.push_back(nums[0]);

        int LIS = 1;
        for (int i = 1; i < nums.size(); i++) {
            if (dp.back() < nums[i]) {
                dp.push_back(nums[i]);
                LIS++;
                continue;
            }

            int idx = lower_bound(dp.begin(),
                                  dp.end(), nums[i]) - dp.begin();
            dp[idx] = nums[i];
        }

        return LIS;
    }
};