9.5 Longest Increasing Subsequence (LIS)

Demo: Longest Increasing Subsequence — LC 300 (Medium — Google/Meta/Microsoft High)

Statement (Demo): Given an integer array nums, return the length of its longest strictly increasing subsequence, in O(n log n). Example: nums=[10,9,2,5,3,7,101,18] → 4 (2→3→7→101) | ⚡ n ≤ 2500, -10⁴ ≤ nums[i] ≤ 10⁴

Approach (O(n log n), patience sorting): tails[i] = the smallest possible last value of an increasing subsequence of length i+1 — this array stays sorted. For each number, binary search the first position >= x and replace it (append if none).

function lengthOfLIS(nums) {
  const tails = [];
  for (const x of nums) {
    let lo = 0,
      hi = tails.length;
    while (lo < hi) {
      // first tails[i] >= x
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x; // replace or append
  }
  return tails.length;
}

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