300 - Longest Increasing Subsequence

Difficulty: Medium | Pattern: Dynamic Programming / Binary Search | Company tags: Amazon, Google, Microsoft, Facebook, Apple

Problem Statement

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

A subsequence is a sequence derived from the array by deleting some elements without changing the relative order of the remaining elements.

Example 1:

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

Example 2:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

Example 3:

Input: nums = [7, 7, 7, 7, 7]
Output: 1

Constraints: 1 <= nums.length <= 2500; -10^4 <= nums[i] <= 10^4

Approach 1: DP — O(n²)

Key insight: dp[i] = length of LIS ending at index i. For each i, look back at all j < i where nums[j] < nums[i], and take the max dp[j] + 1.

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n  # every element is an LIS of length 1 by itself
    
    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)

Dry Run (O(n²))

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

i	nums[i]	dp[i]	Extends which j?
0	10	1	(none)
1	9	1	(none, 10 > 9)
2	2	1	(none)
3	5	2	j=2: 2 < 5, dp[2]+1=2
4	3	2	j=2: 2 < 3, dp[2]+1=2
5	7	3	j=3: 5 < 7, dp[3]+1=3 (also j=4: 3 < 7, dp[4]+1=3)
6	101	4	j=5: 7 < 101, dp[5]+1=4
7	18	4	j=5: 7 < 18, dp[5]+1=4

max(dp) = 4 ✓

Approach 2: Patience Sorting — O(n log n)

Key insight: Maintain a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1.

For each number:

• If it's larger than all tails, append it (extend the longest subsequence)
• Otherwise, binary search for the leftmost tail ≥ number and replace it (maintain the smallest possible tails for each length)

The answer is len(tails).

Algorithm Flow

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    
    return len(tails)

Patience sorting trace for [10, 9, 2, 5, 3, 7, 101, 18]:

num	tails before	action	tails after
10	[]	append	[10]
9	[10]	replace pos=0	[9]
2	[9]	replace pos=0	[2]
5	[2]	append	[2, 5]
3	[2, 5]	replace pos=1	[2, 3]
7	[2, 3]	append	[2, 3, 7]
101	[2, 3, 7]	append	[2, 3, 7, 101]
18	[2, 3, 7, 101]	replace pos=3	[2, 3, 7, 18]

Length = 4 ✓

Note: tails is not the actual LIS — it's a structure that tells you the length. Reconstructing the actual subsequence requires additional bookkeeping.

Edge Cases

• Single element → LIS length 1
• All decreasing → LIS length 1
• All equal → LIS length 1 (strictly increasing means equal is not allowed)
• Already sorted → LIS length = n

Complexity

Approach	Time	Space
DP	O(n²)	O(n)
Patience sorting	O(n log n)	O(n)

Key Terms

Term	Definition
Dynamic programming (DP)	Solving dp[i] = LIS length ending at index i by combining answers to smaller subproblems (dp[j] for j < i).
Subsequence vs. subarray	A subsequence preserves relative order but need not be contiguous, unlike a subarray.
Patience sorting	A card-game-inspired technique that maintains piles (tails) whose sizes track the LIS length in O(n log n).
Binary search (bisect_left)	Used to find, in O(log n), the leftmost position in tails where the current number can replace an existing tail.
tails array invariant	tails is always sorted, and tails[k] holds the smallest possible tail value of any increasing subsequence of length k+1.

FAQ

Q: Why is the tails array not the actual longest increasing subsequence? A: tails only tracks the smallest tail value achievable for each subsequence length — its contents can end up being a mix of digits from different subsequences, not one contiguous valid subsequence.

Q: Can this be solved with a plain greedy approach without any DP or binary search? A: No — a naive greedy that only ever extends the current run and never reconsiders past choices fails on inputs like [1, 5, 2, 3, 4]: greedily taking 1, 5 blocks discovery of the longer [1, 2, 3, 4]. The patience-sorting method fixes this by replacing tail values so future extensions stay possible, which is what makes it correct.

Q: How would you reconstruct the actual LIS, not just its length? A: Keep a parent/predecessor array during the DP approach (O(n²)), or augment the patience-sorting approach with an index array tracking which element preceded each tails update, then backtrack from the last updated position.

Q: What if the problem asked for a non-strictly increasing (non-decreasing) subsequence? A: Change nums[j] < nums[i] to nums[j] <= nums[i] in the DP approach, and use bisect_right instead of bisect_left in the patience-sorting approach.

Q: What's the typical interviewer follow-up? A: Ask for the O(n log n) solution after you present O(n²), and possibly follow up with "Russian Doll Envelopes," a 2D generalization of LIS.

Quick Revision

• Goal: length of the longest strictly increasing subsequence (order preserved, not necessarily contiguous).
• DP approach: dp[i] = 1 + max(dp[j] for j < i where nums[j] < nums[i]); answer is max(dp). O(n²).
• Patience sorting approach: maintain tails, where tails[k] = smallest tail of any LIS of length k+1.
• For each number: append if larger than all tails, else binary-search and replace the leftmost tail ≥ it.
• Answer is len(tails) — note tails itself is not a valid LIS, just a length tracker.
• All-equal or all-decreasing arrays give LIS length 1; a sorted array gives LIS length n.
• Time/space: O(n²)/O(n) for DP; O(n log n)/O(n) for patience sorting.
• Reconstructing the actual subsequence needs extra bookkeeping (parent pointers) in either approach.

Related Problems

• "Russian Doll Envelopes" — 2D extension of LIS (sort by one dimension, then run LIS on the other).
• "Number of Longest Increasing Subsequences" — DP variant that also counts how many LIS's of the max length exist.
• "Longest Common Subsequence" — related subsequence DP pattern comparing two sequences instead of finding an increasing run in one.