Longest Increasing Subsequence — O(n log n) Patience Sorting

Problem

Return the length of the longest strictly increasing subsequence of nums.

Example: [10,9,2,5,3,7,101,18] → 4 ([2,3,7,101])

Approach 1 — O(n²) DP

dp[i] = max(dp[j]+1 for j<i if nums[j]<nums[i]). O(n²).

Approach 2 — O(n log n) Patience Sorting

Maintain tails array: tails[i] = smallest tail element of all increasing subsequences of length i+1. Binary search to find position.

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

Solutions

Python — O(n log n)

import bisect
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails=[]
        for n in nums:
            pos=bisect.bisect_left(tails,n)
            if pos==len(tails): tails.append(n)
            else: tails[pos]=n
        return len(tails)

Python — O(n²)

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

C++

class Solution {
public:
    int lengthOfLIS(vector<int>& nums){
        vector<int> tails;
        for(int n:nums){
            auto it=lower_bound(tails.begin(),tails.end(),n);
            if(it==tails.end()) tails.push_back(n);
            else *it=n;
        }
        return tails.size();
    }
};

Java

class Solution {
    public int lengthOfLIS(int[] nums){
        List<Integer> tails=new ArrayList<>();
        for(int n:nums){
            int lo=0,hi=tails.size();
            while(lo<hi){int mid=(lo+hi)/2;if(tails.get(mid)<n)lo=mid+1;else hi=mid;}
            if(lo==tails.size()) tails.add(n);
            else tails.set(lo,n);
        }
        return tails.size();
    }
}

Complexity

O(n log n) patience sorting | Space: O(n)

Key Takeaway

The tails array isn't the actual LIS, just the lengths. bisect_left finds insertion point.