LeetCode Longest Increasing Subsequence: DP and Patience

LeetCode 300 — Longest Increasing Subsequence — is the gateway DP problem and the gateway patience-sorting problem in one prompt. There are two solutions worth knowing, and they teach different lessons. The O(n^2) DP teaches you to articulate a recurrence. The O(n log n) version teaches you to spot a classical algorithm hiding under a different name.

The Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps relative order but does not need to be contiguous.

Brute Force

Try every subset and check whether it is strictly increasing.

def lengthOfLIS(nums):
    best = 0
    for mask in range(1 << len(nums)):
        pick = [nums[i] for i in range(len(nums)) if mask & (1 << i)]
        if all(pick[i] < pick[i + 1] for i in range(len(pick) - 1)):
            best = max(best, len(pick))
    return best

O(2^n * n). Useful only for sanity-checking on n <= 20.

Optimal Solution

There are two clean optima.

O(n^2) dynamic programming

Define dp[i] as the length of the longest increasing subsequence that ends exactly at index i. The recurrence is dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]), defaulting to 1.

def lengthOfLIS(nums):
    if not nums:
        return 0
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(n log n) patience sorting

Maintain a tails array where tails[k] is the smallest possible tail value of any increasing subsequence of length k + 1 seen so far. For each new number, binary-search for the first tail that is greater than or equal to it and overwrite it. Append if no such tail exists.

from bisect import bisect_left

def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

The contents of tails are not an actual increasing subsequence — that is the most common mistake. The length is correct; the values are aggregates from different candidate subsequences.

Walk Through an Example

Take nums = [10, 9, 2, 5, 3, 7, 101, 18].

Patience version step by step:

• 10 -> tails [10].
• 9 -> replace 10. Tails [9].
• 2 -> replace 9. Tails [2].
• 5 -> append. Tails [2, 5].
• 3 -> replace 5. Tails [2, 3].
• 7 -> append. Tails [2, 3, 7].
• 101 -> append. Tails [2, 3, 7, 101].
• 18 -> replace 101. Tails [2, 3, 7, 18].

Answer: 4. One witnessing LIS is [2, 3, 7, 18] or [2, 3, 7, 101] — note that the final tails array happens to be a valid LIS here, but in general it need not be.

Edge Cases

• Empty array — return 0.
• Strictly decreasing input — the answer is 1; tails has length 1 throughout.
• All equal values — strictly increasing rules out duplicates, so the answer is 1.
• Single element — answer is 1.
• Non-strict variants — use bisect_right instead of bisect_left to allow equal values.

Complexity Analysis

The O(n^2) DP costs O(n^2) time and O(n) space. The patience version costs O(n log n) time and O(n) space.

For inputs up to a few thousand the DP is fine and easier to defend. Past that, patience wins outright. For more on what these complexity classes feel like in practice, the Big-O notation post has the framing.

How to Explain It in an Interview

Open with the DP definition: “dp[i] is the length of the longest increasing subsequence ending at index i.” Derive the recurrence and the time bound. Then volunteer the upgrade: “I can do this in n log n by maintaining the smallest possible tail of any increasing subsequence of each length. Each new number either extends the tails array or replaces the first tail it could fit under.”

If the interviewer asks “is tails the LIS?” — clearly say no, and explain that you would have to reconstruct using parent pointers stored alongside.

If they ask to reconstruct the LIS, fall back to the DP version with a prev[i] array — it is the path of least surprise.

Related Problems

• LeetCode 354 — Russian Doll Envelopes (LIS after a clever sort)
• LeetCode 673 — Number of Longest Increasing Subsequences
• LeetCode 1671 — Minimum Removals to Make Mountain Array
• LeetCode 646 — Maximum Length of Pair Chain

Each builds on LIS by adding a wrapper — sorting, counting, or pairing. The classic LIS engine sits at the core.

Related practice

LIS is the headline example of a one-dimensional DP that admits an algorithmic upgrade. If you want more DP scaffolding before tackling it, the Classic DP Problems post walks through several smaller examples.

Wrap up

LIS is the rare problem where the O(n log n) version is short enough that interviewers expect it. Burn the patience-sorting code into muscle memory and explain why the tails array is a length-witness rather than an actual subsequence. Once you can articulate both solutions and their trade-offs in 90 seconds, LIS goes from a feared question to a routine win.