☕ DSA Java Articles

Topics › Dynamic Programming › DP on LIS

Longest Increasing Subsequence - (DP-43)

Medium TUF ID 2851 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

This is the “LIS using binary search” lecture (DP-43) of the DP series. Given an integer array a, return the length of its longest strictly increasing subsequence, but now for large inputs: with n up to 10^5, the O(n^2) DP performs about 10^10 steps and is too slow. The goal is O(n log n).

Example 1

a = [10, 9, 2, 5, 3, 7, 101, 18]
answer = 4          // 2, 3, 7, 18

Example 2

a = [1, 7, 8, 4, 5, 6, -1, 9]
answer = 5          // 1, 4, 5, 6, 9

Example 2 is the instructive one. After reading 1, 7, 8 the best subsequence is 1, 7, 8, but the eventual answer abandons 7, 8 for 4, 5, 6. A fast method must keep the cheaper option 1, 4 alive without forgetting that length 3 was already reachable.

Approach 1: Quadratic DP (baseline)

Intuition. Let dp[i] be the length of the LIS ending at index i. It is 1 plus the best dp[j] over earlier j with a[j] < a[i], or 1 if there is none. The answer is the maximum dp[i]. This is correct and simple, but every element looks at all earlier ones.

static int quadraticDp(int[] a) {
    int n = a.length, best = 0;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return best;
}

Complexity. Time O(n^2), space O(n).

Approach 2: Better, one array of tails

Intuition. Imagine keeping, as we scan, a list of candidate increasing subsequences. A new element x can extend any candidate whose last value is below x, or start a new one. That explodes, but most candidates are pointless. Among all increasing subsequences of the same length, only the one with the smallest last value matters: anything that can extend a subsequence ending in a larger value can also extend one ending in a smaller value.

So keep a single array tails, where tails[k] is the smallest last value of any increasing subsequence of length k + 1 found so far. Two facts make it easy to maintain:

  1. tails is strictly increasing. A subsequence of length k + 2 ending at value v contains a subsequence of length k + 1 ending below v, so tails[k] < tails[k + 1].
  2. A new value x changes exactly one entry. Let pos be the first index with tails[pos] ≥ x. For shorter lengths, tails[k] < x already, so x cannot improve them. Length pos + 1 can now end at x (extend the length-pos subsequence ending at tails[pos - 1] < x, or take x alone when pos = 0), and x ≤ tails[pos], so x becomes the new tails[pos]. Longer lengths cannot end at x, because that would need a length-pos + 1 subsequence ending below x. If no entry is ≥ x, x extends the longest subsequence and is appended.

Since the size of tails grows exactly when a longer subsequence becomes possible, the final size is the LIS length. In this approach the position is found with a plain left-to-right scan.

static int linearTails(int[] a) {
    List<Integer> tails = new ArrayList<>();
    for (int x : a) {
        int k = 0;
        while (k < tails.size() && tails.get(k) < x) k++;             // first tail >= x
        if (k == tails.size()) tails.add(x);                          // x extends the longest subsequence
        else tails.set(k, x);                                         // x is a cheaper ending for length k + 1
    }
    return tails.size();
}

Complexity. Time O(n · L), where L is the LIS length: fast when L is small, still O(n^2) for sorted input. Space O(L).

Intuition. Fact 1 says tails is sorted, and we are looking for the first entry ≥ x. That is exactly the lower bound of x, which binary search finds in O(log n). Replace or append as before.

Algorithm.

  1. len = 0.
  2. For each x: binary search tails[0..len-1] for the first index lo with tails[lo] ≥ x (lo = len if none).
  3. Set tails[lo] = x; if lo == len, increment len.
  4. Return len.
static int binarySearchTails(int[] a) {
    int[] tails = new int[a.length];
    int len = 0;
    for (int x : a) {
        int lo = 0, hi = len;                                         // search tails[0..len-1]
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1; else hi = mid;
        }
        tails[lo] = x;                                                // lo == len means append
        if (lo == len) len++;
    }
    return len;
}

Dry run on a = [1, 7, 8, 4, 5, 6, -1, 9]:

x lower bound position action tails
1 0 append [1]
7 1 append [1, 7]
8 2 append [1, 7, 8]
4 1 (7 ≥ 4) replace 7 [1, 4, 8]
5 2 (8 ≥ 5) replace 8 [1, 4, 5]
6 3 append [1, 4, 5, 6]
-1 0 (1 ≥ -1) replace 1 [-1, 4, 5, 6]
9 4 append [-1, 4, 5, 6, 9]

The answer is 5. Notice two things. When 4 replaced 7, the length 3 was not lost: tails[2] = 8 still recorded it, while 4 made a cheaper length-2 ending available, which 5 and 6 then used. And the final array [-1, 4, 5, 6, 9] is not a subsequence of a, because -1 comes after 6. Only its length is meaningful.

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

Approach 4: TreeSet variant

Intuition. Because tails holds distinct, sorted values, a TreeSet can store it. ceiling(x) returns the smallest element ≥ x, which is the lower bound; remove it and insert x. If there is no ceiling, inserting x appends it. The set size is the answer. This is handy when you prefer library calls over a hand-written binary search, at the cost of boxing and a larger constant factor.

static int treeSetTails(int[] a) {
    TreeSet<Integer> tails = new TreeSet<>();
    for (int x : a) {
        Integer ceil = tails.ceiling(x);                              // smallest tail >= x
        if (ceil != null) tails.remove(ceil);
        tails.add(x);
    }
    return tails.size();
}

Complexity. Time O(n log n), space O(n).

Variant: longest non-decreasing subsequence

If equal values may follow each other, the same method works with one change: search for the first tail strictly greater than x (the upper bound). Then an equal value is appended after its copy instead of replacing it. For [2, 2, 2] this returns 3, and for [1, 3, 2, 2, 4] it returns 4 (1, 2, 2, 4).

static int longestNonDecreasing(int[] a) {
    int[] tails = new int[a.length];
    int len = 0;
    for (int x : a) {
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (tails[mid] <= x) lo = mid + 1; else hi = mid;          // upper bound instead of lower bound
        }
        tails[lo] = x;
        if (lo == len) len++;
    }
    return len;
}

Edge cases and pitfalls