Longest Increasing Subsequence — From O(n²) DP to O(n log n) Patience Sorting

Problem Statement#

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

Constraints:

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Example 1:

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101]. Length = 4.

Example 2:

Input:  nums = [0, 1, 0, 3, 2, 3]
Output: 4
Explanation: LIS is [0, 1, 2, 3] or [0, 1, 3] — length 4. Wait: [0,1,2,3] requires 3 then 2, but 3>2. Correct LIS: [0,1,3] length 3... or [0,1,2,3]: 0<1<0? No. Answer: [0,1,2,3] from indices 0,1,4... 0<1 yes, 1<3 yes (skip 0 at index 2), 3 is last. LIS = [0,1,3] = length 3. Actually: indices 0,1,3,5: 0<1<3<3? No, strictly increasing. LIS = [0,1,2,3] doesn't work. Answer is 4: [0,1,2,3] from values 0(idx 0),1(idx1),2(idx4 — value 2),3(idx5). Yes: 0<1<2<3.

Example 3:

Input:  nums = [7, 7, 7, 7]
Output: 1
Explanation: No two elements are strictly increasing. Any single element is a valid LIS.

Why This Problem Matters#

Longest Increasing Subsequence (LeetCode 300) is one of the most important classic DP problems and appears across FAANG interviews. Amazon uses it in online assessments. Google asks it in onsites to test knowledge of the O(n log n) optimization. Microsoft includes it as a medium-difficulty question in algorithm interviews.

LIS is also a gateway problem: mastering it unlocks Russian Doll Envelopes (LC 354), where 2D LIS requires a clever sort + 1D LIS reduction. The patience sorting insight — maintaining a "tails" array with binary search — is a non-obvious algorithmic idea that demonstrates sophisticated algorithmic thinking.

The problem is also interesting because it has two well-known approaches with very different complexities and rationales: the O(n^2) DP and the O(n log n) binary search. Both are expected knowledge in FAANG interviews.

The Core Insight#

O(n^2) DP approach:

Define dp[i] as the length of the longest increasing subsequence that ends at index i. Then:

dp[i] = max(dp[j] + 1 for all j < i where nums[j] < nums[i])

The base case is dp[i] = 1 for all i (every single element is a valid LIS of length 1). The answer is max(dp).

O(n log n) Patience Sorting approach:

Maintain an array tails where tails[k] is the smallest possible tail element of all increasing subsequences of length k + 1 seen so far.

For each number num:

• Binary search tails for the first element >= num (using bisect_left).
• If found at position pos, replace tails[pos] = num (we found a subsequence of length pos+1 with a smaller tail).
• If not found (pos == len(tails)), append num (we extended the longest subsequence).

The length of tails at the end is the LIS length. The tails array itself is not the actual LIS — it is a "virtual" array that tracks the optimal tail for each subsequence length.

Why binary search works: tails is always sorted in increasing order (provable by induction). So binary search for the insertion position is always valid.

Building the DP Solution#

Step 1 — Naive Recursion (Exponential)#

# Python — naive recursion, exponential — illustrative only
def lengthOfLIS(nums):
    n = len(nums)
    def dp(i, prev_val):
        if i == n:
            return 0
        # Skip nums[i]
        skip = dp(i + 1, prev_val)
        # Include nums[i] if it is greater than prev_val
        include = 0
        if nums[i] > prev_val:
            include = 1 + dp(i + 1, nums[i])
        return max(skip, include)
    return dp(0, float('-inf'))

This has exponential states due to the combination of position and previous value.

Step 2 — Top-Down Memoization (O(n^2) time, O(n^2) space)#

# Python — top-down memoization
from functools import lru_cache
 
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
 
        @lru_cache(maxsize=None)
        def dp(i: int) -> int:
            """Length of LIS ending at index i."""
            best = 1
            for j in range(i):
                if nums[j] < nums[i]:
                    best = max(best, dp(j) + 1)
            return best
 
        return max(dp(i) for i in range(n))

// JavaScript — top-down memoization
var lengthOfLIS = function(nums) {
    const n = nums.length;
    const memo = new Map();
 
    function dp(i) {
        if (memo.has(i)) return memo.get(i);
        let best = 1;
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) best = Math.max(best, dp(j) + 1);
        }
        memo.set(i, best);
        return best;
    }
 
    let result = 0;
    for (let i = 0; i < n; i++) result = Math.max(result, dp(i));
    return result;
};

Step 3 — Bottom-Up Tabulation (O(n^2) time, O(n) space)#

# Python — bottom-up O(n^2) DP
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n  # each element alone is a valid LIS of length 1
 
        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)

// JavaScript — bottom-up O(n^2) DP
var lengthOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
 
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
 
    return Math.max(...dp);
};

Optimized Solution#

The O(n log n) patience sorting approach:

# Python — O(n log n) patience sorting with bisect
import bisect
 
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails = []  # tails[k] = smallest tail of all LIS of length k+1
 
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)   # extend the LIS
            else:
                tails[pos] = num    # replace with smaller tail
 
        return len(tails)

// JavaScript — O(n log n) patience sorting with binary search
var lengthOfLIS = function(nums) {
    const tails = [];
 
    function bisectLeft(arr, target) {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
 
    for (const num of nums) {
        const pos = bisectLeft(tails, num);
        if (pos === tails.length) tails.push(num);
        else tails[pos] = num;
    }
 
    return tails.length;
};

Visual Dry Run#

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

O(n^2) DP trace:

max(dp) = 4.

O(n log n) patience sorting trace:

len(tails) = 4. Note: [2, 3, 7, 18] is NOT the actual LIS — the actual LIS is [2, 3, 7, 101] (or [2, 3, 7, 18]). tails is just a construct to track the length efficiently.

Complexity Analysis#

For n = 2500: O(n^2) = 6.25 million operations — acceptable. O(n log n) = ~28,000 — much faster.

Common Mistakes#

1. Thinking tails is the actual LIS. tails is not the LIS — it is a virtual array tracking the optimal tail for each length. After processing, the actual LIS elements may not be in tails. Only the length is correct.

2. Using bisect_right instead of bisect_left for strictly increasing. For strictly increasing sequences, you want to replace the first element >= num (not > num). bisect_left finds the first element >= num, which is correct for strict inequality.

3. Using >= instead of > in the O(n^2) DP. The condition is nums[j] < nums[i] (strictly less than). Using <= allows equal elements, which violates the "strictly increasing" requirement.

4. Initializing dp[i] = 0 instead of 1. Each element alone is a valid LIS of length 1. Initialize dp = [1] * n.

5. Returning max(dp) when dp might be empty. For n >= 1, dp is never empty. But if you use max(dp) in an edge case where n = 0, handle it separately (though the constraints say n >= 1).

6. Not understanding why tails is always sorted. The invariant is: tails is strictly increasing at all times. This is maintained because bisect_left always replaces an element that is >= num with num, which is strictly smaller, preserving the sorted property.

Interview Tips#

Present the O(n^2) DP first. "I define dp[i] as the LIS length ending at index i. dp[i] = 1 + max(dp[j]) for all j < i where nums[j] < nums[i]. This is O(n^2)." This shows DP fluency.

Then introduce the patience sorting optimization. "I can improve to O(n log n) using patience sorting. I maintain a tails array where tails[k] is the smallest tail of all increasing subsequences of length k+1. Binary search gives the insertion position."

Explain why tails is sorted. "The tails array is always strictly increasing. I replace the first element greater than or equal to num, making it smaller — which maintains the sorted order."

Clarify that tails is not the LIS. "The elements in tails are not the actual LIS — they are just the optimal tails. The length of tails is the LIS length."

Follow-up Questions#

Q: How do you reconstruct the actual LIS, not just its length? For the O(n^2) DP: track a parent array alongside dp. When dp[i] is updated from j, set parent[i] = j. Reconstruct by following parent pointers from the argmax of dp.

Q: What if the sequence needs to be non-strictly increasing (allowing equal elements)? Use bisect_right instead of bisect_left in the patience sorting approach. In the O(n^2) DP, change < to <=.

Q: How does Russian Doll Envelopes (LC 354) use LIS? Sort envelopes by width ascending, height descending. Then find LIS on heights. The descending height sort prevents using two envelopes of the same width in the same LIS (since their heights form a decreasing sequence).

Q: Can LIS be solved in O(n) time? No known O(n) algorithm exists for general LIS. O(n log n) is optimal for comparison-based sorting. Special cases (like bounded integers) may allow O(n) using counting sort + DP.

Q: What is the connection between LIS and patience sorting in card games? In the card game Patience, you place cards in piles such that each pile has decreasing values (or you start a new pile). The number of piles equals the LIS length — this is the Card Playing Analogy for Dilworth's theorem.

Key Takeaways#

• O(n^2) DP: dp[i] = max(dp[j] + 1) for all j < i with nums[j] < nums[i]. Initialize dp = [1] * n. Answer = max(dp).
• O(n log n) Patience Sorting: maintain tails (always sorted). For each num, use bisect_left to find the insertion position and replace or append. len(tails) is the LIS length.
• tails is not the actual LIS — it is a virtual tracking array. Only its length is meaningful.
• For strictly increasing LIS, use bisect_left (not bisect_right). For non-decreasing LIS, use bisect_right.
• The O(n^2) solution is acceptable for n up to 2500 (per constraints). The O(n log n) solution is required for larger inputs.
• LIS is the foundation for Russian Doll Envelopes (2D LIS reduction), increasing subsequence counting, and various sequence optimization problems.