· By John Kavanagh

Longest Increasing Subsequence in TypeScript: From Lengths to Tails

Concrete steps rising diagonally across a monochrome building facade.
Image by Sebastian Schuster, licensed from Unsplash.

For [4, 2, 5, 3, 7, 6, 8], you can keep [2, 3, 6, 8] and discard the rest. The kept values increase, their original order survives, and the answer is four. Finding that example by eye is easy. Explaining why a short binary‑search loop always finds the right length takes a little more care.

LeetCode's Longest Increasing Subsequence problem asks for that length. I'd start with the quadratic dynamic‑programming solution, even if the final submission uses binary search. It gives us something straightforward to reason about before introducing an array whose name, tails, is rather less informative than its job.


What We're Allowed to Keep

A subsequence can skip values, but it cannot change their order. It doesn't have to be a contiguous subarray. Sorting the input would destroy precisely the information we're trying to preserve: [3, 1, 2] has an answer of two, even though sorting produces three increasing values.

Increasing means strictly increasing. Equal values don't extend a sequence, so [2, 2, 2] has length one. Negative numbers need no special treatment; the ordinary numeric comparison still works.

The official problem supplies between one and 2,500 integers, each between ‑10,000 and 10,000. Both functions below also return zero for an empty array, a small extension beyond that input range. They assume ordinary finite integers, not sparse arrays or NaN. TypeScript's number annotation doesn't validate those assumptions at runtime.


Start with a Sequence Ending Here

Let lengths[i] mean the longest increasing subsequence that ends at index i. Every value can stand alone, which gives each position an initial length of one.

Now inspect each earlier position j. If nums[j] < nums[i], a sequence ending at j can accept nums[i] as its next value. Its length becomes lengths[j] + 1. Take the largest of those candidates, leaving the initial one alone when no earlier value fits.

This is the same habit I use in my Coin Change walkthrough: give the stored answer a precise meaning before writing the transition. Here, "ending at this index" is doing real work. A good subsequence elsewhere in the array might end with a value too large to extend.

export const longestIncreasingSubsequenceDp = (
  nums: readonly number[]
): number => {
  const lengths = new Array<number>(nums.length).fill(1);
  let longest = 0;

  for (let i = 0; i < nums.length; i += 1) {
    for (let j = 0; j < i; j += 1) {
      if (nums[j]! < nums[i]!) {
        lengths[i] = Math.max(lengths[i]!, lengths[j]! + 1);
      }
    }

    longest = Math.max(longest, lengths[i]!);
  }

  return longest;
};

For the opening example, lengths becomes [1, 1, 2, 2, 3, 3, 4]. The 3 at input index three can extend the earlier 2, but not the earlier 4 or 5. The final 8 can extend a length‑three sequence ending in either 7 or 6.

Why is checking earlier positions enough? Any increasing subsequence ending at i either contains only that value or has a penultimate index j with a smaller value. The loop considers every such j, and their answers are already complete. Taking the best extension therefore covers every possible ending at i. The largest recorded length is the answer for the whole array.

The nested loops inspect n(n - 1) / 2 pairs, giving O(n²) time and O(n) extra space. The non‑null assertions reflect the loop bounds and the fully initialised length array; they don't validate external data. The readonly parameter also makes the intention clear: neither implementation sorts or otherwise changes the input.


Give Each Length the Smallest Ending

For finding the length, we don't need to remember every possible ending. Suppose we've found two length‑three subsequences, one ending in 7 and another in 6. Any later value that extends the first can extend the second. Some values, such as another 7, can extend only the second.

So keep the smaller ending. Define tails[k] as the smallest final value we've seen for an increasing subsequence of length k + 1. Each slot summarises a different length. It is not a commitment to one chosen sequence.

Those tail values are strictly increasing. A length‑three subsequence contains a length‑two prefix ending below its final value; the best available length‑two ending is no larger than that prefix's ending. That gives us an ordered array to search without sorting the input.

For each incoming value, find the first tail greater than or equal to it. Replace that tail with the incoming value. If no tail qualifies, append a new slot, increasing the best length by one.


Find the Replacement Position

This is a lower‑bound search: find the first position where tails[position] >= value. I covered a different first‑success search in my Koko Eating Bananas article. The useful connection is the ordered false‑then‑true condition, although here we're searching the tail values rather than candidate eating speeds.

export const longestIncreasingSubsequence = (
  nums: readonly number[]
): number => {
  const tails: number[] = [];

  for (const value of nums) {
    let left = 0;
    let right = tails.length;

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2);

      if (tails[middle]! < value) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    tails[left] = value;
  }

  return tails.length;
};

The interval is half‑open: left is included and right is excluded. A tail below the incoming value cannot be the replacement position, so the search moves past it. Otherwise, that position remains a candidate and everything to its right can be discarded. When the bounds meet, left is either the first qualifying position or the array's length. The midpoint always refers to an existing element, which justifies its non‑null assertion.

For the opening input, the successive arrays are [4], [2], [2, 5], [2, 3], [2, 3, 7], [2, 3, 6], and [2, 3, 6, 8]. Replacing 7 with 6 doesn't lengthen anything yet. It improves the ending available to a later value.

The equality matters. An incoming 2 replaces an existing 2; it doesn't create another slot. Searching for the first strictly greater tail would instead allow duplicates to extend the sequence, solving a different problem.


Why Replacing a Tail is Safe

If the replacement position is k, every earlier tail is smaller than the incoming value. For k > 0, the subsequence represented by slot k - 1 existed before this value arrived, so we can extend it to length k + 1. At k = 0, the new value simply starts a length‑one subsequence.

Replacing a larger ending with a smaller one cannot remove a future extension: anything larger than the old ending is also larger than the new one. An equal replacement changes nothing. When the insertion point is at the end, we've constructed a subsequence one element longer. When it is inside the array, the unchanged later slots still represent subsequences that were found earlier.

Together, those observations preserve the meaning of every slot and make the number of slots the best length. Each of n values performs a binary search over at most n tails, giving O(n log n) time and O(n) extra space in the worst case. That describes how the work grows; it isn't a promise that this version wins every tiny‑input timing test.


The Tails Array isn't the Sequence

Take [2, 6, 3, 4, 1, 5]. The algorithm finishes with [1, 3, 4, 5], but that is not a subsequence of the input: the 1 arrived after the 3 and 4. The correct length is still four, witnessed by [2, 3, 4, 5].

The bookkeeping is allowed to mix endings from different histories. Returning tails would be a very convincing‑looking wrong answer. To reconstruct a sequence, you'd also store input indices and predecessor links, then follow those links backwards from the final tail. That is additional work beyond this length‑only problem.


Check the Cases That Distinguish the Rules

These examples exercise both implementations. The repeated values catch the wrong comparison, the decreasing values catch accidental sorting, and the empty case records our extra behaviour explicitly.

const lisExamples: Array<[number[], number]> = [
  [[], 0],
  [[7], 1],
  [[2, 2, 2], 1],
  [[5, 4, 3, 2], 1],
  [[-4, -2, -3, -1], 3],
  [[4, 2, 5, 3, 7, 6, 8], 4],
  [[2, 6, 3, 4, 1, 5], 4],
];

for (const [input, expected] of lisExamples) {
  for (const solve of [longestIncreasingSubsequenceDp, longestIncreasingSubsequence]) {
    const actual = solve(input);
    if (actual !== expected) {
      throw new Error(`Unexpected length ${actual} for ${JSON.stringify(input)}`);
    }
  }
}

For independent verification, I also enumerated every subsequence of short inputs, rejected any that weren't strictly increasing, and compared the largest remaining length with both functions. That is deliberately slower than either implementation, but it doesn't depend on their reasoning. Larger seeded inputs and the official length limit get separate checks. Agreement on those tests is useful evidence, not proof for every possible array.

My Dynamic Programming Comparison Lab lets you run both versions against that subsequence‑enumeration check. Try the [2, 6, 3, 4, 1, 5] counterexample and inspect the recorded tails: the length agrees with the exhaustive result, even though the final tails don't form a valid subsequence. It's a useful way to separate the answer we're calculating from the bookkeeping used to calculate it.


Wrapping Up

I'd keep the quadratic version whilst learning this problem: its state is easy to explain and it makes a useful comparison. The binary‑search version earns its extra reasoning by discarding endings that cannot improve a future result. Once that meaning is clear, replacing a value in tails stops looking suspicious. Just resist the temptation to return the array.

Downloadable Resource

  • Dynamic Programming Comparison Lab

    Run my fourteen TypeScript solutions across seven problems, with independent checks for string edits, decoding counts, staircase routes, prefixes, and subsequences.

    Download ZIP

Planning a platform change?

I help teams make difficult platform work clearer, from architecture decisions and migrations to launch recovery, performance, and search visibility.