LIS Visualization for Coding Interviews

Longest increasing subsequence — O(n²) DP + patience-sort O(n log n).

Concept

The Longest Increasing Subsequence problem asks for the length (or content) of the longest strictly increasing subsequence of a given sequence. It is one of the canonical dynamic programming problems and a common interview staple because it admits two strikingly different solutions: an O(n^2) DP that mirrors the problem statement, and an elegant O(n log n) patience-sort algorithm that feels like a magic trick until you see why it works. LIS shows up inside scheduling problems, diff algorithms (where it is the backbone of the longest common subsequence between arrays with distinct keys), airline seating optimization, and puzzles involving nested envelopes. Mastering both approaches teaches you to recognize when a greedy-with-binary-search trick can collapse a quadratic DP.

How it works

The O(n^2) DP defines dp[i] as the length of the LIS ending at index i. The recurrence is dp[i] = 1 + max(dp[j]) for all j < i with a[j] < a[i], defaulting to 1 if no such j exists. A second pass computes the answer as max(dp). Reconstruction stores a parent pointer per cell. The O(n log n) patience algorithm keeps an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1 seen so far. For each new value x, binary search for the first index in tails with a value >= x and overwrite it with x. If x is larger than all tails, append it. The length of the LIS is the length of tails at the end. The invariant is that tails is always strictly increasing, so binary search is valid, and smaller tails give more room for future values to extend — that is why we greedily replace. Note: tails is not itself the LIS, only its length; reconstructing the actual subsequence requires parent links.

Implementation

import java.util.Arrays;

public final class LIS {
    private LIS() {}

    public static int lengthOfLISdp(int[] a) {
        int n = a.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int best = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
            }
            if (dp[i] > best) best = dp[i];
        }
        return best;
    }

    public static int lengthOfLISpatience(int[] a) {
        int n = a.length;
        if (n == 0) return 0;
        int[] tails = new int[n];
        int size = 0;
        for (int x : a) {
            int lo = 0, hi = size;
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }
}

Complexity

• DP Time: O(n^2)
• Patience Time: O(n log n)
• Space: O(n)

Common pitfalls

• Confusing the tails array with the actual LIS — it is not the subsequence, only the invariant.
• Using 'strictly increasing' when the problem asks for 'non-decreasing' — swap < for <=.
• Forgetting to initialize dp to 1; a single-element subsequence has length 1.
• Reconstructing the LIS from tails without parent links — it will produce wrong output.
• Linear scan for max at the end ignores that the answer could end at any index.

Key design decisions & trade-offs

• DP vs patience sort — Chosen: Patience for large n. n log n vs n^2 — patience wins above a few thousand elements; DP is simpler to explain.
• Strict vs non-strict — Chosen: Depends on problem statement. Use lower_bound for strict, upper_bound for non-decreasing; getting it wrong silently yields wrong answers.
• Store LIS vs just length — Chosen: Only store parents if needed. Parent reconstruction adds O(n) space and complexity; many uses only need the length.

Practice problems

• Longest Increasing Subsequence

Interview follow-ups

• Reconstruct the actual LIS using parent pointers in the patience version.
• Solve Longest Bitonic Subsequence (increasing then decreasing) via two LIS passes.
• Use LIS to compute minimum deletions to make an array sorted.
• Apply LIS to Russian Doll Envelopes after sorting by width.

Why it matters

LIS is a core part of the Dynamic Programming toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".

Related

• Longest Common Subsequence
• Binary Search
• Edit Distance