Longest Increasing Subsequence

Intuition

The direct dynamic program sets dp[i] = 1 + max(dp[j]) over all earlier j with nums[j] < nums[i], which is correct but runs in O(n^2). We can do better by tracking only what matters: the smallest possible tail value for an increasing subsequence of each length. Keep an array tails where tails[k] is the smallest value that can end an increasing subsequence of length k + 1. For each new number, binary-search for the first tail that is greater than or equal to it; replacing that tail keeps future extension options as open as possible, while appending when the number exceeds every tail grows the best length. The tails array itself is always sorted, which is exactly what makes the binary search valid. The final answer is simply the length of tails, since that equals the length of the longest increasing subsequence we could build.

Algorithm walkthrough

1. 1Start with an empty tails array that will stay sorted throughout the scan.
2. 2For each number, binary-search tails for the leftmost position whose value is >= the current number.
3. 3If that position is past the end of tails, the number extends the longest chain so far, so append it.
4. 4Otherwise overwrite tails at that position, lowering the tail for that length without changing the count.
5. 5Because tails stays sorted and minimal, each replacement preserves correctness for later numbers.
6. 6After processing every number, the length of tails is the length of the longest strictly increasing subsequence.

Implementation

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            lo, hi = 0, len(tails)
            while lo < hi:
                mid = (lo + hi) // 2
                if tails[mid] < num:
                    lo = mid + 1
                else:
                    hi = mid
            if lo == len(tails):
                tails.append(num)
            else:
                tails[lo] = num
        return len(tails)