Frontend Beauty
ESC

Type to search the knowledge base.

Longest Increasing Subsequence

LIS length — classic O(n²) DP and O(n log n) patience sorting with binary search tails array.

intermediate3 min read
  • dsa
  • dp
  • interview
  • Google
  • Meta

The problem

Return the length of the longest strictly increasing subsequence (not necessarily contiguous).

[10,9,2,5,3,7,101,18] → 4  // 2,3,7,101
[0,1,0,3,2,3] → 4
[7,7,7,7] → 1

O(n²) DP

dp[i] = LIS length ending at index i.
dp[i] = 1 + max(dp[j] for j < i and nums[j] < nums[i]), or 1.

function lengthOfLIS(nums: number[]): number {
  const n = nums.length;
  const dp = new Array<number>(n).fill(1);
  let best = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return n ? best : 0;
}
Time O(n²)
Space O(n)

O(n log n): tails + binary search

tails[len-1] = smallest tail of all increasing subsequences with length len.

For each x:

  • If x larger than all tails → append (LIS grows)
  • Else replace the first tail ≥ x (lower_bound) — keeps tails increasing and minimal
function lengthOfLISFast(nums: number[]): number {
  const tails: number[] = [];

  for (const x of nums) {
    let lo = 0;
    let hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(x);
    else tails[lo] = x;
  }
  return tails.length;
}
Time O(n log n)
Space O(n)

Note: tails is not the LIS itself — only its length is correct. Reconstructing the actual sequence needs parent pointers / extra bookkeeping.

Walk [10,9,2,5,3,7,101,18]

x tails
10 [10]
9 [9]
2 [2]
5 [2,5]
3 [2,3]
7 [2,3,7]
101 [2,3,7,101]
18 [2,3,7,18]

length 4.

Edge cases

  • Empty
  • All equal → 1
  • Strictly decreasing → 1
  • Strictly increasing → n

Common mistakes

  • Non-strict (<=) when problem wants strict
  • Thinking tails array is one valid LIS
  • Binary search upper vs lower bound off-by-one

Interview delivery

  1. Subsequence not subarray.
  2. O(n²) DP first.
  3. Patience sorting O(n log n).
  4. Clarify reconstruction if asked.
  5. Complexities.

Mental model

O(n²) DP is the teaching version. O(n log n) maintains the smallest possible tail for every LIS length — patience sorting. Interviewers often accept n² for n≤1e3 and want n log n for n≤1e5.

Reconstructing the sequence

Length-only tails don’t store a real subsequence. Keep prev[i] parent indices during n² DP, or pair values with indices in the n log n method with extra arrays.

Out-loud answer

“LIS length, strict increase. DP O(n²): dp[i] max over prior smaller ends. Faster: tails + binary search lower_bound, O(n log n). tails length is answer, not the sequence itself.”

Further reading