Longest increasing subsequence

Overview

The longest increasing subsequence (LIS) is the longest subsequence whose values strictly increase. For [10, 9, 2, 5, 3, 7, 101, 18] the length is 4 (for example 2, 3, 7, 18). The simple DP computes dp[i] = length of the LIS ending at index i by checking all earlier j with a smaller value: O(n^2).

The O(n log n) solution keeps an array tails where tails[k] is the smallest possible ending value of an increasing subsequence of length k + 1. For each number, binary search the first tail >= it and replace that tail (or append). The length of tails is the LIS length. This 'patience sorting' idea is a classic interview upgrade.

When to use it

• Longest chain where each element must be bigger than the previous.
• Nesting problems after sorting: envelopes, boxes, pairs.
• Minimum deletions to make an array sorted (n - LIS).
• Counting how many longest increasing subsequences exist.

Problem patterns it solves

Where it is used in real software

Key terms

dp[i]

Length of the LIS that ends exactly at index i.

tails[k]

Smallest tail value of any increasing subsequence of length k + 1.

Lower bound

First index in tails with value >= x (strictly increasing LIS).

Strict vs non-decreasing

Use lower bound for strict, upper bound for non-decreasing.

How it works, step by step

1. 1
   O(n^2): initialize dp[i] = 1

   Every element alone is an increasing subsequence.

2. 2
   O(n^2): extend from smaller earlier values

   For j < i with nums[j] < nums[i], dp[i] = max(dp[i], dp[j] + 1).

3. 3
   O(n log n): binary search tails

   For each x, find the first tail >= x.

4. 4
   Replace or append

   If found, replace it with x (a smaller tail is better for the future); otherwise append x.

5. 5
   Answer

   tails.length. Note tails itself is not necessarily a valid subsequence.

O(n^2) dp table for the same input

nums = [10, 9, 2, 5, 3, 7, 101, 18]

max(dp) = 4. The O(n^2) version is easier to extend (counting LIS, reconstruction); the tails version is faster for n up to 10^5.

Implementation

1function lengthOfLIS(nums) {2  const tails = [];3  for (const x of nums) {4    let lo = 0, hi = tails.length;5    while (lo < hi) {             // lower bound: first tail >= x6      const mid = (lo + hi) >> 1;7      if (tails[mid] < x) lo = mid + 1;8      else hi = mid;9    }10    tails[lo] = x;                // replace or append (lo === tails.length)11  }12  return tails.length;13}14 15// O(n^2) with reconstruction16function lisSequence(nums) {17  const n = nums.length;18  const dp = new Array(n).fill(1), prev = new Array(n).fill(-1);19  let bestEnd = 0;20  for (let i = 0; i < n; i++) {21    for (let j = 0; j < i; j++) {22      if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {23        dp[i] = dp[j] + 1;24        prev[i] = j;25      }26    }27    if (dp[i] > dp[bestEnd]) bestEnd = i;28  }29  const seq = [];30  for (let i = bestEnd; i !== -1; i = prev[i]) seq.push(nums[i]);31  return seq.reverse();32}33 34// 354. Russian Doll Envelopes: sort width asc, height desc, then LIS on heights35function maxEnvelopes(envelopes) {36  envelopes.sort((a, b) => a[0] - b[0] || b[1] - a[1]);37  return lengthOfLIS(envelopes.map((e) => e[1]));38}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Returning tails as the actual LIS.

  Fix: tails holds the smallest endings per length and may not be a real subsequence.

• Wrong bound for strict vs non-strict.

  Fix: Strict: first >= x. Non-decreasing: first > x.

• Sorting envelopes by height ascending on ties.

  Fix: Sort ties by height descending so same-width envelopes cannot chain.

Interview questions

Practice problems