Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence in O(n log n). Keep tails, where tails[k] is the smallest possible tail of an increasing subsequence of length k+1. For each number, binary-search the first tail ≥ it and replace it (or append if none).

Traced input: nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4. Original problem: neetcode.io/problems/longest-increasing-subsequence

Complexity

One binary search per element. The O(n²) DP is the simpler alternative.

Key idea

• A smaller tail is always better: it leaves more room for future numbers.
• tails stays sorted, so binary search applies.
• Replacing doesn't change the length; appending extends the best length by one.
• tails isn't an actual subsequence, but its length is the answer.

Common mistakes

• Using > instead of >= in the search allows equal values (non-strict LIS).
• Returning tails as the subsequence; it isn't one.

Solution

int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int i = 0; i < nums.length; i++) {
        int x = nums[i];
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = x;
        if (lo == size) size++;
    }
    return size;
}

def lengthOfLIS(nums: List[int]) -> int:
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

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();
}

Edge cases

Each one has its own trace in the interactive view.