Longest Increasing Subsequence

Problem

Find the length of the longest strictly increasing subsequence.

Example: [10, 9, 2, 5, 3, 7, 101, 18] → length is 4 (e.g., [2, 3, 7, 101])

Naive DP Approach

def lengthOfLIS(nums: List[int]) -> int:
    n = len(nums)
    dp = [1] * n
    
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

Time: O(n²)
Space: O(n)

Optimal: Binary Search Approach

Maintain array ans where ans[i] = smallest tail of any increasing subsequence of length i+1.

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

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

How It Works

Step-by-Step Example

Array: [3, 1, 6, 2, 4, 9, 5, 8, 7]

num=3: ans=[3]
num=1: idx=0 → ans=[1]
num=6: idx=1 → ans=[1,6]
num=2: idx=1 → ans=[1,2]
num=4: idx=2 → ans=[1,2,4]
num=9: idx=3 → ans=[1,2,4,9]
num=5: idx=3 → ans=[1,2,4,5]
num=8: idx=4 → ans=[1,2,4,5,8]
num=7: idx=4 → ans=[1,2,4,5,7]

Return: len(ans) = 5

Why This Works

ans[i] is always the smallest tail for subsequences of length i+1. When we see a new number:

If it’s larger than all tails: Append it (extend the longest subsequence)
If it’s smaller: Replace the first element ≥ it. This improves future chances without changing length.

Key: By always keeping the smallest possible tail, we maximize future extension opportunities.

Lower Bound

lower_bound(num) finds where num would be inserted in sorted ans.

Position ≥ length: Append (new longest)
Position < length: Replace (keep length, improve tail)

Tech Notes

Explorer