longest-increasing-subsequence.ts

/**
 * 300. Longest Increasing Subsequence  (Medium)
 * Link: https://leetcode.com/problems/longest-increasing-subsequence/
 *
 * Return the length of the longest strictly increasing subsequence of `nums`.
 * A subsequence keeps relative order but need not be contiguous.
 *
 * Example:
 *   Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
 *   Output: 4            // [2, 3, 7, 101]
 *
 * Approach:
 *   Patience sorting. Maintain `tails`, where tails[i] is the smallest possible
 *   tail of an increasing subsequence of length i+1. For each number, binary
 *   search the first tail >= it and replace it (or append if larger than all).
 *   The length of `tails` is the answer.
 *
 * Time:  O(n log n)  — binary search per element.
 * Space: O(n)
 */
export function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

  for (const num of nums) {
    // find leftmost index in tails with value >= num
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }

    if (lo === tails.length) tails.push(num);
    else tails[lo] = num;
  }

  return tails.length;
}