Longest Increasing Subsequence

MediumDynamic ProgrammingArrayDynamic ProgrammingBinary Search

Problem

Given an array of integers, find the length of the longest subsequence whose values strictly increase, where the chosen elements keep their original relative order but do not need to be adjacent in the array.

Example. For [10, 9, 2, 5, 3, 7, 101, 18], one longest increasing subsequence is [2, 3, 7, 18], giving a length of 4.

Key idea

Checking every subsequence directly is exponential, since each element can independently be included or excluded. A first improvement defines, for each position, the length of the longest increasing subsequence ending exactly there: one plus the best such length among earlier elements with a smaller value, or just one if none qualify. The largest of these values gives the answer, but scanning every earlier element for each position costs O(n²) overall.

The faster approach maintains a small working list where the value at index k is the smallest possible ending value among all increasing subsequences of length k + 1 built so far. A smaller ending value always leaves more room to extend later, so only that smallest value per length is worth keeping. For each new element, binary search the list for the first entry not smaller than it: replacing that entry preserves the invariant, while an element larger than every entry extends the list by one. The list's final length is the answer, even though the list itself is not a real subsequence from the input.

Solution

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = []; // tails[k] = smallest ending value of any increasing run of length k + 1

  for (const num of nums) {
    let low = 0;
    let high = tails.length;

    // binary search for the leftmost entry not smaller than num
    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (tails[mid] < num) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }

    if (low === tails.length) {
      tails.push(num); // num extends the longest run found so far
    } else {
      tails[low] = num; // num gives an existing run length a smaller ending value
    }
  }

  return tails.length;
}

Complexity

  • Time: O(n log n). One binary search per element against the working list; the straightforward pairwise version runs in O(n²).
  • Space: O(n). The per-position DP array, or the working list in the faster version.

Watch out for

  • The working list in the fast approach is not the actual subsequence; recovering the real sequence needs separate bookkeeping.
  • "Strictly increasing" changes the binary search target compared to "non-decreasing"; check which the problem asks for.
  • The O(n²) pairwise version is simpler to get right and a fine fallback when the input is small.

Pattern

The working-list-plus-binary-search technique is a patience-sorting-style pattern: replace a DP's per-step comparison against every prior state with a lookup against a compact, monotonic summary of the best state achievable at each length.

Related questions