Longest Increasing Subsequence

Approach Summary

Patience sorting with binary search: maintain a tails array. Binary search to find where each element goes.

Full Solution & Approach

The classic O(n²) DP defines dp[i] as the length of the longest increasing subsequence ending at index i, computed as 1 + max(dp[j]) over all j < i with nums[j] < nums[i]. The O(n log n) version is the interview favorite: maintain a tails array where tails[k] is the smallest possible tail value of an increasing subsequence of length k + 1. For each number, binary search for the first tails entry that is at least the number and replace it; if the number is larger than everything, append it. The length of tails is the answer. Replacing entries does not lose solutions — it only keeps the best (smallest) tail for each length, which dominates larger tails. This patience-sorting technique is subtle but is the standard expected solution for the n up to 10⁵ constraints.

Each element performs one binary search over the tails array — O(n log n) time. The tails array grows to at most n — O(n) space.

Solution Code

Solution

import bisect

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

function lengthOfLIS(nums) {
  const tails = [];
  for (const n of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = Math.floor((lo + hi) / 2);
      if (tails[mid] < n) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(n);
    else tails[lo] = n;
  }
  return tails.length;
}

public int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();
    for (int n : nums) {
        int i = Collections.binarySearch(tails, n);
        if (i < 0) i = -(i + 1);
        if (i == tails.size()) tails.add(n);
        else tails.set(i, n);
    }
    return tails.size();
}

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

Edge Cases to Watch

Empty array — return 0
Strictly decreasing array — LIS length 1
All equal values — LIS length 1 (strict inequality required)
Already increasing array — the answer is the full length

How to Recognize This Pattern

LIS length
Strictly increasing subsequence

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)