p58 — Longest Increasing Subsequence

Source: LeetCode 300 · Medium · Topics: DP, Binary Search (patience sort) Companies (2024–2025): Google (very high), Meta (high), Amazon (high), Microsoft (high), Apple (medium-high) Loop position: The canonical “O(n²) DP that also has a O(n log n) algorithm via patience sort.” Tests whether you can derive both AND explain why the faster one works.

1. Quick Context

Given nums[], return the length of the longest strictly-increasing subsequence (not necessarily contiguous).

Two solutions both worth knowing cold:

O(n²) DP

dp[i] = LIS ending at index i. dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). Answer = max(dp).

O(n log n) patience sort

Maintain tails[] where tails[k] = smallest tail of any increasing subseq of length k+1 seen so far. For each x, binary-search for the leftmost tails[k] >= x and overwrite. Answer = len(tails).

The tails array is NOT itself a valid LIS — it’s a smallest-tail-per-length record. But its length equals the LIS length.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/longest-increasing-subsequence/

STOP. 25-min timer. Aim for BOTH solutions.

3. Prerequisite Concepts

• DP with max over predecessors.
• bisect.bisect_left for binary search.
• Subsequence (non-contiguous) vs substring (contiguous).

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Pick a strictly-increasing subset of indices; maximize length.

2. Clarify: Strictly increasing (not ≤)? (Yes on LC 300.) n ≤ 2500 for O(n²); n larger for O(n log n) bonus.

3. Examples:

• [10,9,2,5,3,7,101,18] → 4 (one LIS: [2,3,7,18]).
• [0,1,0,3,2,3] → 4.
• [7,7,7,7] → 1 (strict; ties don’t extend).

5. Brute force: All 2ⁿ subsequences, check increasing. Exponential.

6. Target: O(n²) immediate; O(n log n) for senior+.

7. Pattern: “LIS-on-prefixes” DP + patience-sort variant.

8. Develop: see solution.py.

9. Test: empty; single; strict-increasing; strict-decreasing; all-equal; mixed; LC examples.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The O(n²) DP

For each i, dp[i] = “LIS ending at index i.” Transition: dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), defaulting to 1 if no such j exists. Answer = max(dp).

This is the textbook recurrence; nothing subtle. The clever part is the next algorithm.

6.2 The O(n log n) patience-sort algorithm

Maintain tails[] where tails[k] = smallest possible tail value of any increasing subsequence of length k+1 seen in the prefix processed so far.

For each x in nums:

• pos = bisect_left(tails, x)
• If pos == len(tails): append (extends the longest LIS by 1).
• Else: tails[pos] = x (replaces; we now have a smaller tail for that length).

Answer = len(tails).

bisect_left is key for STRICTLY increasing. Use bisect_right for non-strictly-increasing variants.

6.3 Why patience-sort works — the invariant

Invariant: After processing prefix nums[0..i], tails[k] = the smallest tail value among ALL increasing subsequences of length k+1 drawn from this prefix.

Why preserved:

• Appending x to tails (case pos == len): x is strictly greater than every element in tails, so adjoining it to the best length-len(tails) LIS yields a length-(len(tails)+1) LIS with tail x. This is the only such LIS so far, so x is trivially its smallest tail.
• Replacing tails[pos] with x (case pos < len): x ≤ tails[pos]. We can form a length-(pos+1) LIS ending in x by appending x to any length-pos LIS whose tail is < x (which exists because tails[pos-1] < x by bisect_left’s leftmost condition). So we have a length-(pos+1) LIS with tail x ≤ tails[pos]. Invariant maintained.

Why length suffices: Whenever the prefix’s LIS grows, exactly one append happens. So len(tails) = current LIS length.

6.4 The tails array is NOT an LIS

Common confusion: students print tails and expect a valid LIS. It’s not. Example: nums = [10, 9, 2, 5, 3, 7, 101, 18]. After processing, tails ≈ [2, 3, 7, 18] (which happens to be a real LIS here), but on nums = [4, 10, 4, 3, 8, 9], tails = [3, 8, 9] and the actual LIS is [4, 8, 9] (or [4, 8, 9] from index 0,4,5). The values can drift.

To reconstruct the actual LIS, store predecessor pointers during the patience-sort scan. (Used in solution.py’s lis_reconstruct.)

6.5 Why patience-sort is called “patience sort”

Origin: the card game Patience (Solitaire). Deal cards left-to-right onto piles such that each pile is a decreasing sequence; place each new card on the leftmost pile whose top exceeds it. Number of piles at end = LIS length. (Hammersley, 1972; Aldous & Diaconis, 1995.)

6.6 Variants

• LC 354 Russian Doll Envelopes: 2D LIS. Sort by width ascending, height descending (the trick), then LIS on heights. O(n log n).
• LC 673 Number of LIS: count how many LIS exist. O(n²) extension; cnt[i] alongside dp[i].
• LC 1671 Min Deletions for Bitonic Array: combine forward and backward LIS.
• Longest non-strictly increasing: swap bisect_left → bisect_right.
• Longest decreasing: negate values or reverse comparator.

6.7 Lower bound

LIS cannot be solved faster than O(n log n) in the comparison-based model — provably (Fredman, 1975). Patience sort is asymptotically optimal.

7. Anti-Pattern Analysis

1. Confuse subsequence with substring — substring requires contiguous; LIS does not. Different problem.
2. dp[i] = 1 + max(dp[j] for j < i) without the nums[j] < nums[i] filter — gives length n, wrong.
3. bisect_right for strict LIS — allows duplicates; gives wrong length on [7,7,7].
4. Print tails as the LIS — gives the wrong sequence in general (see 6.4).
5. Reconstruct LIS by reading the DP array greedily — needs predecessor pointers; a simple “walk back from max” is wrong in general.
6. O(n²) when O(n log n) is needed for the constraint — Senior+ candidates lose points if they don’t reach for patience sort when n > 1000.

8. Skills & Takeaways

• bisect_left vs bisect_right for strict vs non-strict bounds.
• The “tails array” abstraction generalizes to many longest-something problems.
• Patience sort connects DP to a non-obvious data-structure-driven O(n log n) algorithm — a recurring theme (e.g., Fenwick-based offline algorithms).
• 2D extension via sort-with-tiebreak (LC 354).

9. When to Move On

• Implement BOTH O(n²) and O(n log n) cold in 20 min.
• Explain the patience-sort invariant in 60 seconds.
• Reconstruct the actual LIS (not just length) on paper.
• Solve LC 354 with the sort-by-width-asc-height-desc trick and explain why.
• Distinguish bisect_left vs bisect_right for strict vs non-strict.

10. Company Context

• Google: L5/L6. O(n log n) expected; lower scores for O(n²) only. Often paired with LC 354 in onsite.
• Meta: E5 onsite. LC 673 (count of LIS) a frequent follow-up.
• Amazon: L6+. Bar Raiser will probe “why O(n log n) works.”
• Microsoft: L65+; LC 1671 bitonic variant.
• Apple: Compiler / ML infra teams; productized as “longest monotone trace in a profiling timeline.”

Scorecard for strong: “Solved both O(n²) and O(n log n), articulated the patience-sort invariant, mentioned the lower bound, sketched LC 354 with the sort trick.”

11. Interviewer’s Lens

12. Level Delta

• Mid (L4): O(n²) DP, correct, handles strict.
• Senior (L5): + O(n log n) patience sort + correct bisect_left.
• Staff (L6): + reconstructs actual LIS + extends to LC 354 (2D) + states the comparison-based lower bound.
• Principal (L7+): + count-of-LIS via Fenwick + connections to RSK correspondence (patience sort ⇄ Young tableaux) + bitonic / longest non-decreasing variants.

13. Follow-up Q&A

Q1: LC 354 Russian Doll Envelopes. Why sort by width ascending, height descending? A1: With equal widths, descending height prevents two envelopes of the same width from chaining in the height-LIS (they cannot doll into each other). Then LIS on the height column = answer.

Q2: How to count the number of LISes (LC 673)? A2: O(n²) DP with two arrays: dp[i] = LIS length ending at i; cnt[i] = number of LISes ending at i. For each j < i with nums[j] < nums[i]:

• If dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1; cnt[i] = cnt[j].
• Elif dp[j] + 1 == dp[i]: cnt[i] += cnt[j]. Answer = sum of cnt[i] where dp[i] == max(dp).

Q3: Reconstruct the actual LIS, not just its length. A3: During the patience-sort pass, store prev[i] = predecessor index for nums[i] in the LIS ending at i. Maintain pile_idx[k] = index of the most recent nums[i] placed at tails[k]. After processing, walk back from the last-appended element via prev[].

Q4: Longest NON-strictly increasing variant. A4: Switch bisect_left → bisect_right. (Allows equal values to extend.)

Q5: Stream version: nums arrive one at a time; emit LIS length after each. A5: Patience sort is naturally online — process each x as it arrives; current LIS length = len(tails). O(log n) amortized per update.

14. Solution Walkthrough

See solution.py:

• lis_n2 — O(n²) DP.
• lis_n_log_n — patience-sort O(n log n).
• lis_reconstruct — patience-sort + predecessor pointers to emit the actual LIS.
• lis_brute — all subsequences, exponential (for stress test n ≤ 12).

15. Beyond the Problem

Principal code review: “LIS is special because it sits at the boundary of three big ideas: DP, monotone data structures, and combinatorial bijections (RSK correspondence). The fact that the same answer falls out of patience sort, a Fenwick-tree count, and the length of the first row of a Young tableau is not coincidence — it’s deep mathematics. You won’t be asked the bijection in an interview, but knowing it exists is what separates a coder from a computer scientist. When you solve LIS, take the extra five minutes to also sketch why the n log n algorithm is optimal — it changes how you think about lower bounds forever.”