Longest Increasing Subsequence

Given an integer array nums, return the length of its longest strictly increasing subsequence.

A subsequence keeps some of the elements (possibly all, at least one) in their original order but may skip any others; the chosen elements do not have to be next to each other. Strictly increasing means every chosen element is larger than the one before it, so equal values cannot both be used.

An O(n²) solution is acceptable to start with; can you reach O(n log n)?

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Pattern Path · Dynamic Programming · problem 155 of 169

Start simple

Try all 2ⁿ subsequences and keep the longest increasing one: O(2ⁿ·n) time. The classic DP over "ends at i" improves this to O(n²).

The key idea

The O(n²) DP sets best[i] = 1 + max(best[j]) over earlier j with nums[j] < nums[i]. It works, but it compares every pair.

The faster idea keeps one number per length: tails[L] is the smallest tail of any increasing subsequence of length L + 1 found so far. A smaller tail is always at least as good, because more future values can extend it. These tails are strictly increasing (a length-3 sequence contains a length-2 prefix with a smaller tail), so tails is sorted.

For each number x, binary-search for the first tail that is >= x. If none exists, x extends the longest subsequence: append it. Otherwise replace that tail with x: there is a sequence of that length ending in something smaller now. Using >= (a lower bound) is what enforces strictly increasing, since an equal value replaces rather than extends.

The answer is the length of tails. Note that tails itself is not necessarily a real subsequence; only its length is meaningful.

Complexity

• Time: O(n log n)
• Space: O(n)

Python

from bisect import bisect_left


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # tails[L] = smallest possible last value of an increasing subsequence of length L + 1
        tails = []
        for x in nums:
            i = bisect_left(tails, x)  # first tail >= x
            if i == len(tails):
                tails.append(x)        # x extends the longest subsequence so far
            else:
                tails[i] = x           # x is a smaller tail for length i + 1
        return len(tails)

JavaScript

var lengthOfLIS = function(nums) {
  // tails[L] = smallest possible last value of an increasing subsequence of length L + 1
  const tails = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length; // find the first tail >= x
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = x; // appends when lo === tails.length, otherwise lowers that tail
  }
  return tails.length;
};

What the interviewer is checking

Interviewers expect the O(n²) DP quickly and then probe whether you can derive the patience-sorting / binary-search optimisation and explain why the tails array stays sorted.

Mistakes to avoid

• Using upper bound (first tail > x), which allows equal values and computes a non-decreasing subsequence.
• Returning best[n-1] in the DP instead of the maximum over all i.
• Assuming tails is an actual increasing subsequence of the input.

Follow-ups to expect

• Reconstruct one longest subsequence. (Store predecessor indices per element.)
• Count how many longest subsequences exist. (DP with lengths and counts.)
• Nest envelopes by width and height. (Sort, then LIS on heights.)

In real software

Diff tools (patience diff) use LIS to align matching lines between file versions, and scheduling or version-ordering problems reduce to finding the longest chain that respects an order.

Practice next