Longest Increasing Subsequence — Patience Sort Binary Search

Problem 329 · Longest Increasing Subsequence

Difficulty: Medium · Pattern: Patience Sort + Binary Search

Find the length of the longest strictly increasing subsequence.

Intuition

Maintain tails[] where tails[i] is the smallest tail element for increasing subsequence of length i+1. For each num, binary search for the insertion point in tails.

Solutions

# Python
import bisect
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails): tails.append(x)
        else: tails[pos] = x
    return len(tails)

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

// C++
int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        auto it=lower_bound(tails.begin(),tails.end(),x);
        if (it==tails.end()) tails.push_back(x); else *it=x;
    }
    return tails.size();
}

Complexity

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