Dynamic Programming
Find the longest subsequence where each element exceeds the previous. O(n log n) via patience sorting with binary search. Generalizes to longest chain, envelope nesting, and similar problems.
LeetCode 300 gives you an array of integers and asks for the length of the longest strictly increasing subsequence. A subsequence can skip elements, so it does not need to be contiguous, but it must preserve the original order. For [10, 9, 2, 5, 3, 7, 101, 18], the answer is 4: one such subsequence is [2, 3, 7, 101].
The naive approach, enumerating all subsequences and checking each one, is obviously impractical. But even smarter brute force (recursion with memoization over "which elements to include") does not lead to a clean solution. The key insight is to define the subproblem around where the subsequence ends, not which elements it contains.
Define dp[i] as the length of the longest increasing subsequence that ends at index i. Every element by itself is a subsequence of length 1, so dp[i] = 1 initially. For each index i, look backward at every index j < i. If nums[j] < nums[i], then we could extend the best subsequence ending at j by appending nums[i]: dp[i] = max(dp[i], dp[j] + 1).
The answer is max(dp[0], dp[1], ..., dp[n-1]), the longest subsequence ending at any position.
def lengthOfLIS(nums):
n = len(nums)
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)Let us trace through [10, 9, 2, 5, 3, 7, 101, 18].
i=0 (10): No elements before it. dp = [1].
i=1 (9): Check j=0: 10 < 9? No. dp = [1, 1].
i=2 (2): Check j=0: 10 < 2? No. j=1: 9 < 2? No. dp = [1, 1, 1].
i=3 (5): Check j=0: 10 < 5? No. j=1: 9 < 5? No. j=2: 2 < 5? Yes. dp[3] = dp[2] + 1 = 2. dp = [1, 1, 1, 2].
i=4 (3): j=2: 2 < 3? Yes. dp[4] = 2. dp = [1, 1, 1, 2, 2].
i=5 (7): j=2: 2 < 7? Yes, dp[5] = 2. j=3: 5 < 7? Yes, dp[5] = 3. j=4: 3 < 7? Yes, dp[5] = max(3, 3) = 3. dp = [1, 1, 1, 2, 2, 3].
i=6 (101): Best predecessor is index 5 with dp=3. dp[6] = 4. dp = [1, 1, 1, 2, 2, 3, 4].
i=7 (18): Best predecessor is index 5 with dp=3. dp[7] = 4. dp = [1, 1, 1, 2, 2, 3, 4, 4].
The answer is max(dp) = 4. This approach is time and space.
The quadratic solution works for small inputs, but many LIS problems have constraints up to or even . At , an solution performs operations, far too slow. We need a fundamentally better algorithm.
Imagine you are playing a card game. You lay cards out left to right. Each card goes on the leftmost pile whose top card is greater than or equal to the current card. If no such pile exists, you start a new pile to the right. This is called patience sorting, and it turns out the number of piles you create equals the length of the LIS.
The "top cards" of the piles form a sorted sequence: this is the tails array. Specifically, tails[i] holds the smallest possible tail element of any increasing subsequence of length i + 1. The array stays sorted at all times, which means we can use binary search to find where each new element belongs.
For each element in the input, binary search the tails array for the leftmost position where tails[pos] >= element. If no such position exists (the element is larger than all tails), append it. This extends the longest subsequence found so far. Otherwise, replace tails[pos] with the element. This does not change the LIS length, but it keeps the tails as small as possible, maximizing the chance that future elements can extend the subsequence.
from bisect import bisect_left
def lengthOfLIS(nums):
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)Each of the n elements requires one binary search on an array of size at most n, so the total time is . Space is for the tails array.
Input: [10, 9, 2, 5, 3, 7, 101, 18].
10: tails is empty, append. tails = [10].
9: bisect_left([10], 9) = 0. Replace tails[0]. tails = [9].
2: bisect_left([9], 2) = 0. Replace tails[0]. tails = [2].
5: bisect_left([2], 5) = 1. That equals len(tails), so append. tails = [2, 5].
3: bisect_left([2, 5], 3) = 1. Replace tails[1]. tails = [2, 3].
7: bisect_left([2, 3], 7) = 2. Append. tails = [2, 3, 7].
101: bisect_left([2, 3, 7], 101) = 3. Append. tails = [2, 3, 7, 101].
18: bisect_left([2, 3, 7, 101], 18) = 3. Replace tails[3]. tails = [2, 3, 7, 18].
The length is 4. Note that tails at the end is [2, 3, 7, 18], which happens to be a valid LIS, but this is not always the case. The tails array is not necessarily an actual subsequence from the input; it is a bookkeeping structure. Its length, however, always equals the LIS length.
This distinction matters. bisect_left finds the leftmost position where the element could be inserted to keep the array sorted. For strictly increasing subsequences, this is what you want: if the element equals an existing tail, you replace it (no duplicate values in a strictly increasing sequence).
bisect_right finds the rightmost such position. If you use bisect_right instead, equal elements will go to the next position, effectively allowing non-strict (non-decreasing) subsequences. So the choice of bisect function directly controls whether your LIS is strictly increasing or allows ties.
from bisect import bisect_left, bisect_right
def lis_strict(nums): # strictly increasing
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
def lis_non_decreasing(nums): # allows equal consecutive elements
tails = []
for num in nums:
pos = bisect_right(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)The tails array gives you the length, but not the actual subsequence. To recover the subsequence, maintain a parallel array of parent pointers. For each element, record which element preceded it in the subsequence. Also record which index in the original array corresponds to each position in tails.
from bisect import bisect_left
def lis_with_reconstruction(nums):
n = len(nums)
tails = []
tails_idx = [] # index in nums for each tails position
parent = [-1] * n # parent pointer for each element
for i, num in enumerate(nums):
pos = bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
tails_idx.append(i)
else:
tails[pos] = num
tails_idx[pos] = i
parent[i] = tails_idx[pos - 1] if pos > 0 else -1
# Backtrack from the last element
result = []
idx = tails_idx[-1]
while idx != -1:
result.append(nums[idx])
idx = parent[idx]
return result[::-1]This still runs in time. The reconstruction step at the end is where k is the LIS length.
For LeetCode 354, you are given envelopes with (width, height) and must find the maximum number you can nest (each envelope must be strictly larger in both dimensions). This reduces to LIS with a clever sorting trick.
Sort the envelopes by width ascending. Now you need the longest increasing subsequence on heights, but there is a catch. Envelopes with the same width cannot nest inside each other. If you sort same-width envelopes by height ascending, the LIS might pick two envelopes with the same width.
The fix: sort by width ascending, but break ties by height descending. With heights in descending order within a width group, the LIS on heights will never pick two envelopes from the same width group (since it needs strictly increasing values, and the heights within a group are sorted in the wrong direction).
from bisect import bisect_left
def maxEnvelopes(envelopes):
envelopes.sort(key=lambda x: (x[0], -x[1]))
# LIS on heights
tails = []
for _, h in envelopes:
pos = bisect_left(tails, h)
if pos == len(tails):
tails.append(h)
else:
tails[pos] = h
return len(tails)The sort is and the LIS is , so the total is .
LeetCode 673 extends the problem: it asks not just for the length of the LIS, but how many distinct LIS there are. This requires tracking counts alongside lengths.
Define dp[i] as the length of the LIS ending at index i (same as before), and count[i] as the number of such subsequences. When you find that dp[j] + 1 > dp[i], you have found a strictly better predecessor, so update dp[i] and set count[i] = count[j]. When dp[j] + 1 == dp[i], you have found another equally good predecessor, so add: count[i] += count[j].
def findNumberOfLIS(nums):
n = len(nums)
dp = [1] * n
count = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
count[i] = count[j]
elif dp[j] + 1 == dp[i]:
count[i] += count[j]
max_len = max(dp)
return sum(c for d, c in zip(dp, count) if d == max_len)This is time. There are more advanced approaches using segment trees or BITs to bring it down to , but the quadratic version is the standard interview solution.
| Variant | Time | Space |
|---|---|---|
| Basic LIS (DP) | ||
| Basic LIS (binary search) | ||
| LIS with reconstruction | ||
| Russian doll envelopes | ||
| Number of LIS |
You're probably looking at LIS when:
a < b and b < c implies a < c), so each item only depends on the best chain ending before it.Common templates:
dp[i] = 1 + max(dp[j] for j < i if nums[j] < nums[i]). Example: Longest Increasing Subsequence.tails array, binary search each element into place. Example: Russian Doll Envelopes (sort then LIS).length[i] and count[i] to tally how many longest chains end at each index. Example: Number of Longest Increasing Subsequence.<. Example: Largest Divisible Subset.Practice Problems (18)