Lab 05 — LIS (Longest Increasing Subsequence)

Goal

Solve LC 300 with two distinct algorithms: the canonical O(N²) DP and the patience-sort + binary-search O(N log N) variant. Internalize why both produce the same answer despite very different mechanics. After this lab you can produce both solutions from a blank screen in <15 minutes total and explain the equivalence on a whiteboard.

Background Concepts

The LIS problem is the canonical example of a problem with two equally-valid algorithmic angles. The O(N²) DP defines dp[i] = length of LIS ending at index i; the O(N log N) algorithm maintains an array tails where tails[k] = smallest tail of any increasing subsequence of length k+1. Both produce the same length; the binary-search version is faster but harder to prove correct.

Patience sorting: imagine dealing cards onto piles such that each pile is strictly decreasing top-to-bottom (place each card on the leftmost pile whose top is ≥ the new card; if none exists, start a new pile). The number of piles equals the LIS length, by Dilworth’s theorem. The tails array tracks the top of each pile.

Interview Context

LIS is a top-20 Medium DP problem and shows up at Google, Bloomberg, and Microsoft regularly. The follow-up “can you do better than O(N²)?” is asked specifically to test whether you know patience sorting. Candidates who know only O(N²) are shipped to L4; candidates who can derive O(N log N) from scratch (or articulate it cleanly) are L5+ material. LIS is also the building block for LC 354 (Russian Doll Envelopes) and LC 673 (Number of LIS).

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Constraints

  • 1 ≤ nums.length ≤ 2500 (canonical LeetCode constraint)
  • −10^4 ≤ nums[i] ≤ 10^4

Clarifying Questions

  1. Strictly increasing or non-decreasing? (Strictly — nums[i] < nums[j].)
  2. Subsequence or subarray? (Subsequence — non-contiguous selections allowed.)
  3. Return the length or the actual sequence? (Length only, per problem.)
  4. Are duplicates handled? (Yes; strict means duplicates can’t both be in the LIS.)
  5. Is the empty subsequence allowed (length 0)? (Yes, but since nums.length ≥ 1, the answer is ≥ 1.)

Examples

[10, 9, 2, 5, 3, 7, 101, 18]    → 4   ([2, 3, 7, 101] or [2, 5, 7, 101])
[0, 1, 0, 3, 2, 3]              → 4   ([0, 1, 2, 3])
[7, 7, 7, 7]                    → 1
[1]                             → 1
[5, 4, 3, 2, 1]                 → 1

Initial Brute Force

For each index, recursively decide include or skip, tracking the previous chosen element to enforce strict-increasing:

def lengthOfLIS_brute(nums):
    def f(i, prev):
        if i == len(nums):
            return 0
        skip = f(i + 1, prev)
        take = 0
        if prev == -1 or nums[i] > nums[prev]:
            take = 1 + f(i + 1, i)
        return max(skip, take)
    return f(0, -1)

Brute Force Complexity

O(2^N) — each step has two choices.

Optimization Path

The state is (i, prev) where prev is the last chosen index (or -1 for none). There are O(N²) such states, so memoization gives O(N²) time and space. Tabulation: define dp[i] = length of LIS ending exactly at index i; recurrence reads only smaller j < i, so we don’t even need the prev dimension — dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). Final answer is max(dp).

For O(N log N): maintain tails such that tails[k] is the smallest tail of any LIS of length k+1. For each nums[i], binary-search for the first element in tails ≥ nums[i]; if found, replace; if not (i.e., nums[i] exceeds all), append.

Final Expected Approach

O(N²) DP: prefix DP indexed by ending position; recurrence iterates over all earlier indices.

O(N log N) patience sort: maintain tails as an increasing array; bisect_left(tails, nums[i]) gives the position to replace; if equal to len(tails), append.

The equivalence: each tails[k] corresponds to “the smallest endpoint of a length-(k+1) IS we’ve seen”. When we process nums[i], replacing tails[k] with nums[i] represents “we’ve found a length-(k+1) IS with smaller tail” — which can only help future extensions. The length of tails at the end is the LIS length.

Data Structures Used

  • 1D dp of size N (O(N²) version).
  • 1D tails array (O(N log N) version), Python’s bisect module.

Correctness Argument

O(N²): by induction. dp[i] = 1 + max(dp[j] : j < i, nums[j] < nums[i]). Base: dp[0] = 1. Inductive step: any LIS ending at i has a previous element at some j < i with nums[j] < nums[i], contributing dp[j] + 1. The max over all valid j is the optimum. Answer is max_i dp[i].

O(N log N) (Patience sort): invariant — tails[k] is the smallest possible tail of any IS of length k+1 over nums[0..i]. When processing nums[i]: binary-search for the leftmost position k with tails[k] >= nums[i]. If k = len(tails), append (we’ve extended the longest IS by one). Otherwise, replace tails[k] with nums[i] (we’ve found a length-(k+1) IS with smaller tail; future extensions are now easier). The invariant is preserved at every step. The length of tails is the LIS length.

Complexity

AlgorithmTimeSpace
Brute forceO(2^N)O(N)
MemoizedO(N²)O(N²)
Tabulated O(N²) DPO(N²)O(N)
Patience sortO(N log N)O(N)

Implementation Requirements

All four stages.

# ---- Stage 1: Brute force ----
def lengthOfLIS_brute(nums):
    def f(i, prev):
        if i == len(nums):
            return 0
        skip = f(i + 1, prev)
        take = 0
        if prev == -1 or nums[i] > nums[prev]:
            take = 1 + f(i + 1, i)
        return max(skip, take)
    return f(0, -1)

# ---- Stage 2: Memoized ----
from functools import lru_cache
def lengthOfLIS_memo(nums):
    @lru_cache(None)
    def f(i, prev):
        if i == len(nums): return 0
        skip = f(i + 1, prev)
        take = 0
        if prev == -1 or nums[i] > nums[prev]:
            take = 1 + f(i + 1, i)
        return max(skip, take)
    return f(0, -1)

# ---- Stage 3: Tabulated O(N^2) ----
def lengthOfLIS_tab(nums):
    n = len(nums)
    if n == 0: return 0
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

# ---- Stage 4: Patience sort O(N log N) ----
from bisect import bisect_left
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails)

Tests

  • [10, 9, 2, 5, 3, 7, 101, 18] → 4.
  • [0, 1, 0, 3, 2, 3] → 4.
  • [7, 7, 7, 7] → 1.
  • [1] → 1.
  • [1, 2, 3, 4, 5] → 5 (already sorted).
  • [5, 4, 3, 2, 1] → 1 (decreasing).
  • N=2500 random — performance test for both algorithms.
  • Cross-check: random N≤15, the four implementations should agree.

Follow-up Questions

  1. “Return the actual LIS, not just the length.” → Track parent pointers in the O(N²) DP, or in O(N log N) keep alongside tails an array tails_idx of indices into nums and parent links.
  2. “Number of distinct LIS’s of maximum length.” (LC 673) → Augment dp[i] with cnt[i] = number of LIS’s ending at i.
  3. “Longest non-decreasing subsequence.” → bisect_right instead of bisect_left.
  4. “2D version: stack envelopes (LC 354).” → Sort by width ascending and height descending (to break ties); run LIS on heights.
  5. “Longest bitonic subsequence.” → Compute LIS forward and LIS backward; combine at each split point.

Product Extension

LIS underlies version-history compression, longest-monotonic-trend analysis in time-series (e.g., longest streak of growing daily users), and dependency-resolution heuristics. The O(N log N) algorithm is what production code uses when N is large.

Language/Runtime Follow-ups

  • Python: bisect_left is in the standard library and uses C-level binary search — extremely fast.
  • Java: Arrays.binarySearch(tails, 0, size, x) returns negative for not-found; convert to insertion point with -(ret + 1).
  • Go: sort.SearchInts(tails, x) for bisect_left equivalent.
  • C++: lower_bound(tails.begin(), tails.end(), x) for bisect_left; upper_bound for bisect_right.
  • JS/TS: no built-in binary search — implement manually or use a third-party lodash.sortedIndex.

Common Bugs

  1. bisect_right vs bisect_left — strict-increasing uses bisect_left; non-decreasing uses bisect_right. Off-by-one in this choice silently gives the wrong LIS variant.
  2. Treating tails as the actual LIS — it isn’t; it’s just the smallest-tails-by-length array. Reconstructing the LIS requires extra bookkeeping.
  3. O(N²) DP: starting dp[i] = 0 instead of 1 — every element is itself an LIS of length 1.
  4. Returning dp[N-1] instead of max(dp) — the LIS may end anywhere, not necessarily at the last index.
  5. Memoization on (i, prev) with prev=-1 not recognized as initial state — works in Python with @lru_cache since -1 is hashable, but easy to forget.

Debugging Strategy

For [10, 9, 2, 5, 3, 7, 101, 18]: trace tails after each element: [10] → [9] → [2] → [2,5] → [2,3] → [2,3,7] → [2,3,7,101] → [2,3,7,18]. Length 4 is the LIS length. If your trace diverges, you’ve made a bisect mistake. For the O(N²) DP, print dp after the loop: [1,1,1,2,2,3,4,4].

Mastery Criteria

  • Recognized “longest increasing subsequence” as LIS within 30 seconds.
  • Wrote the brute recursion in <2 minutes.
  • Wrote the O(N²) DP from blank screen in <4 minutes.
  • Wrote the O(N log N) patience-sort version in <5 minutes.
  • Articulated the patience-sort invariant (“tails[k] is the smallest tail of length-(k+1) IS”) in <30 seconds.
  • Stated O(N log N) time complexity and explained why binary-search is correct here.
  • Solved LC 300 unaided in <12 minutes (both algorithms).
  • Solved LC 354 (Russian Doll Envelopes) by reduction to LIS in <15 minutes.
  • Articulated bisect_left vs bisect_right for strict vs non-strict in <30 seconds.