Longest Increasing Subsequence: From O(n²) DP to O(n log n)

Given an array nums, return the length of its longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

Examples

Input	Output	Why
`nums = [10, 9, 2, 5, 3, 7, 101, 18]`	`4`	For example 2, 3, 7, 18.
`nums = [0, 1, 0, 3, 2, 3]`	`4`	0, 1, 2, 3.
`nums = [7, 7, 7]`	`1`	Strictly increasing: equal values do not count.

Constraints

1 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹

Hints

Hint 1

The quadratic solution: best[i] is the length of the longest increasing subsequence ending at i, the maximum of best[j] + 1 over earlier, smaller nums[j]. Interviewers ask for something faster.

Hint 2

Two increasing subsequences of the same length are not equally useful: the one ending on the smaller value can be extended by more future elements.

Hint 3

Keep tails[L] = the smallest value on which an increasing subsequence of length L + 1 ends. The tails are increasing, so each new value can be placed by binary search: it replaces the first tail that is at least as large, or extends the list.

Where people lose marks

Using an upper bound for a strictly increasing subsequence. Equal values would then extend the list: [7, 7, 7] would give 3 instead of 1.
Returning the tails array as the subsequence. Its length is right; its contents are not a subsequence of nums in general.
Thinking the replacement loses information. Overwriting a tail with a smaller value never shortens any achievable length; it only makes more futures possible.
Writing the binary search with an off-by-one on the end. Search over the whole current length, including the position just past the last tail.

Dry run on `[10,9,2,5,3,7,101,18]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 8

Step 1 / 8

nums
100i91225334751016187
tails (by length)
100
longest so far1
10 is larger than every tail, so it extends the longest run: there is now an increasing subsequence of length 1.
Step 2 / 8

nums
10091i225334751016187
tails (by length)
90
longest so far1
9 replaces the tail 10 for length 1: a run of that length can now end on a smaller value, which leaves more room for later elements.
Step 3 / 8

nums
1009122i5334751016187
tails (by length)
20
longest so far1
2 replaces the tail 9 for length 1: a run of that length can now end on a smaller value, which leaves more room for later elements.
Step 4 / 8

nums
100912253i34751016187
tails (by length)
2051
longest so far2
5 is larger than every tail, so it extends the longest run: there is now an increasing subsequence of length 2.
Step 5 / 8

nums
10091225334i751016187
tails (by length)
2031
longest so far2
3 replaces the tail 5 for length 2: a run of that length can now end on a smaller value, which leaves more room for later elements.
Step 6 / 8

nums
1009122533475i1016187
tails (by length)
203172
longest so far3
7 is larger than every tail, so it extends the longest run: there is now an increasing subsequence of length 3.
Step 7 / 8

nums
10091225334751016i187
tails (by length)
2031721013
longest so far4
101 is larger than every tail, so it extends the longest run: there is now an increasing subsequence of length 4.
Step 8 / 8

nums
10091225334751016187i
tails (by length)
203172183
longest so far4
18 replaces the tail 101 for length 4: a run of that length can now end on a smaller value, which leaves more room for later elements. The answer is the number of tails: 4.

How to think about it

The standard dynamic program looks back over every earlier element and costs O(n²). The faster version changes the state. Instead of "the best length ending here", keep, for every length, the best ending value:

tails[L] = the smallest value on which some increasing subsequence of length L + 1, among the elements seen so far, ends.

Two facts make this fast.

The tails increase. A subsequence of length L + 2 contains one of length L + 1 ending on a smaller value, so tails[L] < tails[L + 1].
Each new value changes one tail. A value x extends every subsequence whose tail is below x; the longest such gives a new candidate tail for the next length. That is the first position whose tail is at least x: overwrite it with x, or append x if no tail is that large.

Finding that position is a binary search, so the whole pass is O(n log n). The length of tails at the end is the answer. The array itself is not, in general, a valid subsequence: it mixes values from different candidates, which is a classic follow-up question.

For "strictly increasing", search for the first tail that is at least x (a lower bound). For "non-decreasing", search for the first tail greater than x (an upper bound). Changing that one comparison is the whole difference.

Complexity. Time O(n log n) · Space O(n)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

from bisect import bisect_left

def longest_increasing(nums):
    tails = []                      # tails[L]: smallest end of an increasing run of length L + 1
    for x in nums:
        k = bisect_left(tails, x)   # first tail >= x (strictly increasing)
        if k == len(tails):
            tails.append(x)         # x extends the longest run
        else:
            tails[k] = x            # a run of length k + 1 can now end lower
    return len(tails)

#include <vector>
#include <algorithm>

int solve(const std::vector<int>& nums) {
    std::vector<int> tails;                 // tails[L]: smallest end of a run of length L + 1
    for (int x : nums) {
        auto it = std::lower_bound(tails.begin(), tails.end(), x);   // first tail >= x
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    return static_cast<int>(tails.size());
}

class Solution {
    public int longestIncreasing(int[] nums) {
        int[] tails = new int[nums.length];    // tails[0..len): smallest ends by length
        int len = 0;
        for (int x : nums) {
            int lo = 0, hi = len;               // first tail >= x
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1; else hi = mid;
            }
            tails[lo] = x;
            if (lo == len) len++;
        }
        return len;
    }
}

function longestIncreasing(nums) {
  const tails = [];                       // tails[L]: smallest end of a run of length L + 1
  for (const x of nums) {
    let lo = 0, hi = tails.length;        // first tail >= x
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < x) lo = mid + 1; else hi = mid;
    }
    tails[lo] = x;                        // extends when lo === tails.length
  }
  return tails.length;
}

fn solve(nums: &[i64]) -> usize {
    let mut tails: Vec<i64> = Vec::new();   // tails[l]: smallest end of a run of length l + 1
    for &x in nums {
        let k = tails.partition_point(|&t| t < x);   // first tail >= x
        if k == tails.len() {
            tails.push(x);
        } else {
            tails[k] = x;
        }
    }
    tails.len()
}

import qualified Data.Set as S

-- The tails, kept as a set: inserting x and deleting the smallest element greater than x
-- leaves the set holding exactly the tails, because they are strictly increasing.
solve :: [Int] -> Int
solve = S.size . foldl place S.empty
  where
    place tails x = case S.lookupGE x tails of
      Nothing -> S.insert x tails                      -- x extends the longest run
      Just t  -> S.insert x (S.delete t tails)         -- replace the first tail >= x

Variants to try

Return one longest subsequence: store, for each element, the index of the element it extended, then walk back from the end.
Russian-doll envelopes: sort by width ascending and, for equal widths, height descending; then the answer is the LIS of the heights.
Count the longest increasing subsequences: the O(n²) dynamic program carrying a count alongside each length, or a Fenwick tree for O(n log n).
Minimum deletions to make an array sorted: n minus the length of its longest non-decreasing subsequence.

Next problems

Medium15 min

Longest increasing subsequence in O(n log n)