Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence.

Find the length of the longest strictly increasing subsequence. The optimized solution is famous because it replaces explicit subsequence tracking with a 'smallest tail' array.

ArrayDPBinary Search

Pattern fit

The classic entry solution is DP because each position asks for the best increasing subsequence ending there, while the optimized version teaches how binary search can compress the state frontier.

Key observation

The optimized solution does not store an actual subsequence. It stores the smallest possible tail value for each length, which preserves future extension potential.

Target complexity

O(n log n) / O(n)

How to break down the solution cleanly

Maintain tails[i] = the smallest possible tail value of an increasing subsequence of length i + 1.

For each number, binary-search the first position in tails whose value is >= current number.

Replace that position with the current number, because a smaller tail is always better for future extension.

If the number is larger than all tails, append it and grow the LIS length.

Walk through one example

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

tails evolves as [10] -> [9] -> [2] -> [2, 5] -> [2, 3] -> [2, 3, 7] -> [2, 3, 7, 101] -> [2, 3, 7, 18].

The final tails length is 4, so LIS length is 4.

Reference implementation

Python

from bisect import bisect_left

def lengthOfLIS(nums: list[int]) -> int:
    tails: list[int] = []

    for value in nums:
        index = bisect_left(tails, value)
        if index == len(tails):
            tails.append(value)
        else:
            tails[index] = value

    return len(tails)

TypeScript version

TypeScript

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

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

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < value) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    if (left === tails.length) {
      tails.push(value);
    } else {
      tails[left] = value;
    }
  }

  return tails.length;
}

What to pay attention to in the code

codetails is not the real subsequence. It is only a compressed frontier for future extension.
codeUse bisect_left / lower_bound semantics so equal values replace rather than extend.

Common pitfalls

warning

Confusing subsequence with contiguous subarray or substring.

warning

Treating the tails array as the actual answer sequence and explaining it incorrectly.

Common follow-ups

How would you explain the O(n^2) DP before jumping to the optimized version?

What extra bookkeeping is needed if the interviewer asks for the subsequence itself?

Continue with related problems

Build repeatable depth inside the Dynamic Programming cluster before moving on.

view_weekBack to the pattern page

#198