Longest Increasing Subsequence

Longest Increasing Subsequence medium

Description

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

A subsequence keeps the relative order of nums but can skip arbitrary elements.

Examples

> Case 1:
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    Output: 4
    Explanation: one LIS is [2, 3, 7, 101].
 
> Case 2:
    nums = [0, 1, 0, 3, 2, 3]
    Output: 4
 
> Case 3:
    nums = [7, 7, 7, 7]
    Output: 1

Constraints

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
Follow-up: can you do it in O(n log n)?

Solution 1 — O(n²) DP

What am I computing? dp[i] = length of the LIS that ends at index i.
Dimensions? One.
Base cases? dp[i] = 1 (any single element is an LIS of length 1).
Transition? Look at every earlier j. If nums[j] < nums[i], we can extend the LIS that ended at j: dp[i] = max(dp[i], dp[j] + 1).
Order? Increasing i.
Answer? max(dp[i]) over all i — the LIS doesn’t have to end at the last element.

Time: O(n²). Space: O(n).

Solution 2 — O(n log n) patience sorting

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

For each x in nums, binary-search for the first tails[k] >= x and replace it with x. If no such k exists, append x to extend the longest run by one.

The length of tails at the end is the LIS length.

tails is not the LIS itself. It’s a clever bookkeeping array. The length of tails is correct, but the values inside may not form a valid subsequence of nums. Reconstructing the actual subsequence requires extra tracking — see “Russian Doll Envelopes” follow-ups.

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

Why does it work? Replacing tails[k] with a smaller value x doesn’t shrink any subsequence — it just makes it easier to extend in the future. The invariant (“tails[k] is the smallest possible tail of any length-k+1 subsequence”) is preserved, and the array’s length only grows when we genuinely found a longer run.

Analysis comparison

Approach	Time	Space	When to use
`O(n²)` DP	`O(n²)`	`O(n)`	Default for small `n`; easiest to reason about; gives `dp[i]` for free if needed
Patience sort	`O(n log n)`	`O(n)`	Required for `n >= ~10^4`; cleaner code; harder to extract actual LIS

Coin Change Longest Common Subsequence