Longest Increasing Subsequence

1. Problem & Core Objective

Return the length of the longest strictly increasing subsequence. A subsequence need not be contiguous.

nums = [10,9,2,5,3,7,101,18]   →  4      [2,3,7,18] or [2,3,7,101]
nums = [0,1,0,3,2,3]           →  4      [0,1,2,3]
nums = [7,7,7,7,7]             →  1      strictly increasing

Constraints: 1 <= nums.length <= 2500 · -10^4 <= nums[i] <= 10^4

What's actually being tested: the O(n²) DP is expected; the O(n log n) patience solution is the differentiator. And the crucial subtlety there — the maintained array is not the answer subsequence, only its length is meaningful.

2. First-Principles Thought Process

The O(n²) recurrence

dp[i] = the length of the longest increasing subsequence ending at index i.

To extend to i, the previous element must be at some j < i with nums[j] < nums[i]:

dp[i] = 1 + max over j < i with nums[j] < nums[i] of dp[j]

with dp[i] = 1 if no such j exists (the element alone).

The answer is max(dp), not dp[n−1] — the longest subsequence needn't end at the last element. That's a real trap: on [1,2,3,0], dp[3] = 1 but the answer is 3.

Why this can't be rolled

dp[i] reads every dp[j] for j < i. Unbounded lookback — the array is required, and O(n²) is the honest bound for this formulation.

Same counterexample as Word Break, and the clearest contrast with the fixed-window recurrences earlier in this section.

The O(n log n) reframe

Maintain tails, where tails[k] is the smallest possible tail value of any increasing subsequence of length k+1.

For each element x:

• binary search for the first entry >= x
• if none, append — x extends the longest subsequence found so far
• otherwise replace that entry with x — a subsequence of that length now ends smaller

The answer is tails.length.

Why keeping the smallest tail is correct

A smaller tail leaves more room for future elements to extend it. If two increasing subsequences have the same length, the one ending smaller is at least as extensible — never worse.

So replacing is safe: it never loses a possible future extension, and it may gain some.

The trap: tails is not the answer

After processing [10,9,2,5,3,7,101,18], tails is [2,3,7,18] — which is increasing and is length 4. But 18 never followed 7 in the input; the real subsequences are [2,3,7,101] and [2,5,7,101].

tails is a bookkeeping array of best-possible tails, not a subsequence. Only its length is meaningful. Reporting it as the answer subsequence would be wrong.

3. Solution Paths

Approach 1 — Try every subsequence (brute force)

public int lengthOfLIS(int[] nums) {
    return lis(nums, 0, Integer.MIN_VALUE);
}

private int lis(int[] nums, int i, int prev) {
    if (i == nums.length) return 0;
    int skip = lis(nums, i + 1, prev);                        // don't take nums[i]
    int take = 0;
    if (nums[i] > prev) take = 1 + lis(nums, i + 1, nums[i]); // take it
    return Math.max(take, skip);
}

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why is this hard to memoise directly?"

The state is (i, prev), and prev is a value rather than an index — so the state space is n times the value range, not n².

You can memoise on (i, prevIndex) instead, which gives O(n²) states. That's the bridge to the O(n²) DP — and it's why the standard formulation indexes by "ending at i" rather than carrying a previous value.

⭐ "What does the take-or-skip shape tell you?"

That it's the same family as House Robber — two branches per element. The difference is that the "take" branch is conditional on nums[i] > prev, which is what makes the state need more than just the index.

Approach 2 — O(n²) DP

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);                                // each element alone is length 1
    int best = 1;

    for (int i = 1; i < n; i++) {
        for (int 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]);                  // the answer may end anywhere
    }
    return best;
}

Trace — nums = [10,9,2,5,3,7,101,18]:

max(dp) = 4 ✓

• Time O(n²) = 6.25 × 10^6 · Space O(n)

Counter-questions on this approach

⭐ "Why is the answer max(dp) rather than dp[n−1]?"

Because dp[i] is the longest subsequence ending at i, and the overall longest needn't end at the last element.

On [1,2,3,0], dp = [1,2,3,1] — the last element is smallest, so dp[3] = 1. Returning dp[n−1] gives 1 instead of 3.

This is the same state-definition issue as in House Robber, in reverse: there dp[i] meant "best over the prefix" so the last cell was the answer; here it means "best ending at i" so it isn't.

⭐ "Why nums[j] < nums[i] and not <=?"

The problem says strictly increasing. With <=, [7,7,7,7,7] would report 5 instead of 1.

If the problem allowed non-decreasing, this single character would change — and in the binary-search version it changes which search variant you use, which is the subtler consequence.

"Why Arrays.fill(dp, 1)?"

Every element is an increasing subsequence of length 1 on its own. Without it the defaults are 0, and an element with no smaller predecessor would report 0 instead of 1.

"Is O(n²) acceptable here?"

At n = 2500 it's 6.25 × 10^6 — comfortably fast. So the O(n log n) version isn't required by the constraints; it's the differentiator if asked to do better.

Approach 3 — Patience sorting with binary search (optimal)

public int lengthOfLIS(int[] nums) {
    List<Integer> tails = new ArrayList<>();

    for (int x : nums) {
        int pos = lowerBound(tails, x);              // first index with tails[idx] >= x
        if (pos == tails.size()) tails.add(x);       // x extends the longest so far
        else tails.set(pos, x);                      // a length-(pos+1) run now ends smaller
    }
    return tails.size();
}

private int lowerBound(List<Integer> tails, int target) {
    int lo = 0, hi = tails.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (tails.get(mid) < target) lo = mid + 1;
        else                          hi = mid;
    }
    return lo;
}

Trace — nums = [10,9,2,5,3,7,101,18]:

Length 4 ✓ — verified against the O(n²) DP.

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

Counter-questions on this approach

⭐ "What does tails[k] actually mean?"

The smallest possible tail value among all increasing subsequences of length k+1 seen so far.

Not "the tail of the best subsequence" — the smallest achievable tail at that length. That's why replacement is correct: finding a length-k+1 run ending smaller strictly improves future extensibility.

⭐ "Why is replacing safe? Doesn't it destroy a subsequence?"

It doesn't destroy anything real — tails was never storing actual subsequences.

The argument: if two increasing subsequences have the same length, the one ending in a smaller value can be extended by strictly more future elements. So keeping the smaller tail never loses a possible extension and may gain some.

The length recorded at each index stays achievable; only the recorded tail improves.

⭐ "Is tails itself a valid answer subsequence?"

No, and this is the trap. After the trace above, tails = [2,3,7,18] — increasing and of the right length, but 18 appears before 101 in tails while appearing after it in the input. The real subsequences of length 4 are [2,3,7,101] and [2,5,7,101].

So tails is bookkeeping, not an answer. Only tails.size() is meaningful.

To recover an actual subsequence you'd record, for each element, the tails index it landed at plus a back-pointer — then walk back from the final append.

⭐ "Why lowerBound (first >= x) rather than upperBound (first > x)?"

Because the requirement is strictly increasing. lowerBound finds the first entry >= x and replaces it — so an equal value is replaced rather than appended, and duplicates never extend the length.

On [7,7,7,7,7], every 7 replaces tails[0] and the answer stays 1 ✓.

If the problem allowed non-decreasing subsequences, you'd use upperBound instead, so an equal value appends. That one-function swap is the entire difference, and it's easy to get backwards.

"Why hi = tails.size() rather than size() - 1?"

Because pos == tails.size() is a meaningful outcome — it means "x is larger than every tail, so append". The search space is the half-open range [0, size], which is the lo < hi / hi = mid convention from Section 5.

"Could Collections.binarySearch be used instead?"

Yes, with care: it returns -(insertionPoint) - 1 when absent, so you'd convert. And for a present element it may return any matching index, which breaks the strict-vs-non-strict distinction. Writing the bound explicitly is clearer and avoids that ambiguity.

Comparison

4. Why the Optimal Wins

The O(n²) DP asks, for each element, "which earlier element should precede me?" — scanning all of them.

The patience method reframes it: instead of tracking the best subsequence ending at each index, track the best tail for each achievable length. That array is sorted by construction, so the search becomes binary rather than linear.

O(n²) → O(n log n), from changing what's being indexed — lengths rather than positions.

The framing worth keeping:

tails[k] is the smallest tail of any increasing subsequence of length k+1. Smaller tails extend more easily, so replacing is always safe — but tails is NOT the answer subsequence, only its length is.

5. Java Prerequisites

The O(n²) recurrence

Arrays.fill(dp, 1);
for (int 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]);          // the answer may end anywhere

Lower bound — first index with tails[idx] >= target:

int lo = 0, hi = tails.size();         // half-open, so pos == size means "append"
while (lo < hi) { int mid = lo + (hi-lo)/2; if (tails.get(mid) < target) lo = mid+1; else hi = mid; }

Strict vs non-strict — lowerBound for strictly increasing, upperBound for non-decreasing. One function swap.

Collections.binarySearch is awkward here — it returns an encoded insertion point when absent and an arbitrary match when present.

6. Interview Communication Guide

Clarifying questions: Strictly increasing or non-decreasing (strictly — it decides which binary-search bound)? Subsequence or subarray (subsequence — non-contiguous)? Return the length or the sequence (length; recovering the sequence is extra work)? Maximum n (2500, so O(n²) passes)?

The pitch

"The standard DP is dp[i] = the longest increasing subsequence ending at index i. To extend to i, the previous element is any j < i with a smaller value, so dp[i] = 1 + max of those dp[j], defaulting to 1.

The answer is max(dp), not dp[n−1] — the longest subsequence needn't end at the last element. On [1,2,3,0] the last cell is 1 while the answer is 3.

That's O(n²) = 6.25 × 10^6 here, which passes comfortably. It also can't be rolled to O(1) space, because dp[i] reads every earlier cell rather than a fixed window.

If asked to do better, there's an O(n log n) method. Maintain an array tails where tails[k] is the smallest possible tail of any increasing subsequence of length k+1. For each element, binary search for the first entry >= x: if there isn't one, append — x extends the longest run; otherwise replace it.

Replacing is safe because a smaller tail is at least as extensible — if two subsequences have the same length, the one ending smaller can be continued by strictly more future elements. So it never loses an option.

The crucial subtlety: tails is not the answer subsequence. On the example it ends as [2,3,7,18], but 18 comes after 101 in the input, so that's not a real subsequence — the actual ones are [2,3,7,101] and [2,5,7,101]. Only tails.size() is meaningful. Recovering an actual subsequence needs back-pointers.

And the bound matters: I use lower bound — first entry >= x — because the problem wants strictly increasing, so an equal value replaces rather than appends. On [7,7,7,7,7] that correctly gives 1. If non-decreasing were allowed, I'd use upper bound instead, and that's the whole difference."

Edge cases to volunteer:

Name [7,7,7,7,7] and [1,2,3,0]. The first pins down strict-vs-non-strict; the second catches returning the last cell instead of the maximum.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the actual subsequence, not just its length."

With the O(n²) DP, track a prev[] index per element and walk back from the argmax. With the patience method it's harder: record for each element the tails position it occupied plus a pointer to the element then at position − 1, then follow the chain back from the last append.

Worth stating that the O(n log n) version makes reconstruction genuinely fiddlier — the array it maintains isn't the answer.

⭐ "Count the number of longest increasing subsequences."

LeetCode 673. Keep a second array count[i] alongside dp[i], incrementing when an equal-length path is found and resetting when a longer one appears. O(n²). The patience method doesn't extend to counting cleanly.

"Allow non-decreasing subsequences."

Change < to <= in the O(n²) DP, and swap lowerBound for upperBound in the patience version. One line either way, but in opposite-looking directions — worth deriving rather than memorising.

"Find the longest DECREASING subsequence."

Negate the values, or reverse the comparison. Same algorithm.

"What if n were 10^5?"

O(n²) is 10^10 — infeasible. The O(n log n) version becomes necessary, which is the threshold where it stops being optional.

"Find the minimum number of increasing subsequences the array can be split into."

By Dilworth's theorem, that equals the length of the longest non-increasing subsequence. A pleasing result: one LIS-style computation answers a partitioning question.