Longest Increasing Subsequence (LIS)
“Finding the longest upward trend in chaos.”
TL;DR
LIS starts with O(N^2) DP where dp[i] stores the LIS length ending at index i. The optimal O(N log N) solution maintains a tails array of smallest tail elements for each LIS length, using binary search (bisect_left) to find insertion points. This is equivalent to patience sorting from card games. The tails array length equals the LIS length, but it is not the actual subsequence. For reconstruction, track parent pointers. The same idea powers git diff --patience and the anchor-chaining step in whole-genome aligners, and it is a handy tool for aligning long transcripts.
1. Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence derived from an array by deleting some or no elements without changing the order of the remaining elements.
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: [0, 1, 2, 3]
2. Approach 1: Dynamic Programming O(N^2)
Intuition:
- Let
dp[i]= length of LIS ending at indexi. - For each
i, look at all previous elementsj < i. - If
nums[j] < nums[i], we can extend the LIS ending atjby includingnums[i]. dp[i] = max(dp[j] + 1)for all validj.
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
n = len(nums)
dp = [1] * n # Every element is an 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)
Complexity:
- Time: O(N^2)
- Space: O(N)
3. Approach 2: Binary Search + Greedy O(N log N)
Key Insight:
- Maintain an array
tailswheretails[i]is the smallest tail element of all increasing subsequences of lengthi+1. - For each new number, use binary search to find where it fits.
Why does this work?
- If we want to build a longer LIS, we should keep the tail as small as possible.
- Example:
[4, 5, 1, 2, 3]- After processing
[4, 5],tails = [4, 5]. 1replaces4→tails = [1, 5].2replaces5→tails = [1, 2].3extends it →tails = [1, 2, 3], so the answer is 3.- Had we kept
[4, 5]as the only candidate,3could not extend anything and we would answer 2.
- After processing
import bisect
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = []
for num in nums:
# Find the leftmost position where num can be placed
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num) # Extend the LIS
else:
tails[pos] = num # Replace to keep tail small
return len(tails)
Complexity:
- Time: O(N log N)
- Space: O(N)
Both versions were checked against a brute-force enumeration on 2,000 random small arrays and agree on every case.
4. Why the Tails Array Stays Sorted
Binary search only works because tails is always sorted. Proof by induction:
- Base case: After the first element,
tails = [nums[0]]. Sorted. - Inductive step: Assume
tailsis sorted before processingx = nums[i], and letpos = bisect_left(tails, x).- If
pos == len(tails), every entry is smaller thanx, so appending keeps the order. - Otherwise
bisect_leftguaranteestails[pos-1] < x(whenpos > 0) andx ≤ tails[pos]. After the replacement,tails[pos-1] < x ≤ old tails[pos] < tails[pos+1], so the array is still sorted.
- If
5. Patience Sorting
The binary search approach is the card game patience sorting in disguise.
Game rules:
- Deal cards one by one.
- Place each card on the leftmost pile whose top card is greater than or equal to it.
- If no such pile exists, start a new pile on the right.
Connection to LIS:
- Number of piles = length of the LIS.
- In the order cards were placed (bottom to top), each pile is non-increasing.
- The top cards of the piles, read left to right, are increasing. They are exactly the
tailsarray.
6. Reconstructing the LIS
The binary search approach only gives the length. To get an actual sequence, remember which index currently ends each length, and give every element a pointer to its predecessor:
import bisect
def findLIS(nums):
if not nums:
return []
n = len(nums)
tails = []
parent = [-1] * n # Track predecessor
tail_indices = [] # Index of the element that ends each tail
for i, num in enumerate(nums):
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
tail_indices.append(i)
else:
tails[pos] = num
tail_indices[pos] = i
# Set parent
if pos > 0:
parent[i] = tail_indices[pos - 1]
# Backtrack to reconstruct LIS
lis = []
k = tail_indices[-1]
while k != -1:
lis.append(nums[k])
k = parent[k]
return lis[::-1]
print(findLIS([10, 9, 2, 5, 3, 7, 101, 18])) # [2, 3, 7, 18]
7. Common Mistakes and Pitfalls
1. Confusing subsequence with subarray:
- Subarray: Contiguous (e.g.,
[2, 5, 3]in[1, 2, 5, 3, 7]). - Subsequence: Non-contiguous (e.g.,
[2, 3, 7]). - Fix: Clarify with the interviewer immediately.
2. Incorrect reconstruction:
- Mistake: Printing the
tailsarray. - Fact:
tailsis NOT the LIS. It stores the smallest tail for each length. - Example: For
[2, 5, 3, 7, 1],tailsends as[1, 3, 7], which is not even a subsequence because1comes last. A real LIS is[2, 3, 7]. - Fix: Use the
parentarray backtracking method.
3. Not handling duplicates:
- “Strictly increasing” vs “non-decreasing”.
- Strictly:
nums[j] < nums[i], andbisect_leftin the binary search version. - Non-decreasing:
nums[j] <= nums[i], andbisect_right.
4. 2D LIS sorting order:
- For envelopes
(w, h), sortingwascending andhascending is wrong. - Why?
[2, 3]and[2, 4]. If sorted ascending, we might pick both. But[2, 3]cannot fit into[2, 4](width must be strictly greater). - Fix: Sort
wascending,hdescending.
8. Variants
8.1 Longest Decreasing Subsequence
Solution 1: Reverse the condition in the DP.
nums = [10, 9, 2, 5]
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] > nums[i]: # Changed from <
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp)) # 3: [10, 9, 2] or [10, 9, 5]
Solution 2: Negate all numbers and find the LIS.
- The LIS of
[-10, -9, -2, -5]is the LDS of[10, 9, 2, 5].
8.2 Number of LIS (LeetCode 673)
Problem: Count how many different LIS exist.
Approach: Extend the DP to track counts.
def findNumberOfLIS(nums):
n = len(nums)
dp = [1] * n # Length of LIS ending at i
count = [1] * n # Number of LIS ending at i
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
if dp[j] + 1 > dp[i]:
# Found a longer LIS
dp[i] = dp[j] + 1
count[i] = count[j]
elif dp[j] + 1 == dp[i]:
# Found another LIS of same length
count[i] += count[j]
max_len = max(dp)
return sum(c for l, c in zip(dp, count) if l == max_len)
print(findNumberOfLIS([1, 3, 5, 4, 7])) # 2
8.3 Russian Doll Envelopes (LeetCode 354)
Problem: You have envelopes (w, h). An envelope can fit into another if both width and height are strictly greater. Find the maximum nesting depth.
Insight: This is 2D LIS.
- Sort by width ascending, height descending (crucial!).
- Find the LIS on heights.
Why descending height?
- If two envelopes have the same width, they can’t nest.
- Sorting heights descending within a width means they can never both appear in one increasing subsequence.
def maxEnvelopes(envelopes):
# Sort by width asc, height desc
envelopes.sort(key=lambda x: (x[0], -x[1]))
# Extract heights
heights = [h for w, h in envelopes]
# Find LIS on heights (Approach 2)
return Solution().lengthOfLIS(heights)
print(maxEnvelopes([[5, 4], [6, 4], [6, 7], [2, 3]])) # 3
8.4 Longest Bitonic Subsequence
A sequence that first increases, then decreases.
- Example:
[1, 11, 2, 10, 4, 5, 2, 1]→[1, 2, 10, 4, 2, 1](length 6).
def longestBitonicSubsequence(nums):
n = len(nums)
# LIS ending at i
lis = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
lis[i] = max(lis[i], lis[j] + 1)
# LDS starting at i
lds = [1] * n
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if nums[j] < nums[i]:
lds[i] = max(lds[i], lds[j] + 1)
# Max of lis[i] + lds[i] - 1
return max(lis[i] + lds[i] - 1 for i in range(n))
print(longestBitonicSubsequence([1, 11, 2, 10, 4, 5, 2, 1])) # 6
8.5 Weighted LIS
Each element has a value and a weight. Maximize the total weight of an increasing subsequence.
def weightedLIS(nums, weights):
n = len(nums)
dp = [0] * n # Max weight ending at i
for i in range(n):
dp[i] = weights[i] # At least include itself
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + weights[i])
return max(dp)
print(weightedLIS([1, 101, 2, 3, 100], [1, 101, 2, 3, 100])) # 106: [1, 2, 3, 100]
8.6 Other relatives
- Longest Divisible Subset (LeetCode 368): the same O(N^2) DP after sorting, with the condition
nums[i] % nums[j] == 0. - Longest alternating subsequence: elements alternate up and down, e.g.
[1, 5, 3, 8, 6, 9](length 6). Solved with two DP arrays (ending on an up step, ending on a down step). - All LIS: compute
dpas in Approach 1, then backtrack from every index withdp[i] == max_len. The output can be exponential in size.
8.7 LIS with a Fenwick tree or segment tree
The O(N^2) DP asks “what is the best dp[j] among earlier elements with a smaller value?”. After compressing values to ranks 1..N, a Fenwick tree (or segment tree) over ranks answers that prefix-maximum query in O(log N), which gives O(N log N) overall. Unlike the tails trick, this version extends directly to weighted LIS and, by storing (length, count) pairs, to counting LIS (LeetCode 673) in O(N log N).
9. Theory
9.1 Connection to Longest Common Subsequence (LCS)
LIS reduces to LCS:
- Make a copy of
nums, sort it and remove duplicates:sorted_nums. - Find the Longest Common Subsequence of
numsandsorted_nums.
sorted_nums is strictly increasing, so any common subsequence is strictly increasing too, and every increasing subsequence of nums is also a subsequence of sorted_nums. Thus LCS(nums, sorted_nums) == LIS(nums). The cost is O(N^2), slower than Approach 2, but the reduction also runs the other way: the Hunt-Szymanski LCS algorithm turns LCS into an LIS over matching position pairs.
9.2 Mirsky’s theorem and the patience piles
Define a partial order on the positions of the array: i precedes j when i < j and nums[i] < nums[j].
- A chain (every pair comparable) is a strictly increasing subsequence.
- An antichain (no pair comparable) is a non-increasing subsequence.
Mirsky’s theorem says the length of the longest chain equals the minimum number of antichains needed to partition the set. For sequences:
The length of the LIS equals the minimum number of non-increasing subsequences needed to cover the array.
Example: [10, 9, 2, 5, 3, 7, 101, 18]
- LIS:
[2, 3, 7, 18](length 4). - Patience sorting builds exactly four piles, each non-increasing:
[10, 9, 2],[5, 3],[7],[101, 18].
Patience sorting is a constructive proof: each pile is a non-increasing subsequence, and the number of piles equals the LIS length.
Its dual, Dilworth’s theorem, swaps the roles: the minimum number of chains needed to cover a poset equals the size of the largest antichain. For sequences, the minimum number of strictly increasing subsequences needed to cover the array equals the length of the longest non-increasing subsequence.
9.3 Lower bounds and faster special cases
- Comparison model: Fredman (1975) showed that any algorithm that only compares elements needs Ω(N log N) comparisons, even just to compute the LIS length. Approach 2 is therefore optimal in that model.
- Integer inputs: If values are integers (after coordinate compression they lie in
[1, N]), the binary search can be replaced by a predecessor query on a van Emde Boas tree, giving O(N log log N) in the word-RAM model. The Hunt-Szymanski LCS work already used this idea for permutations. In practice the constant factors of vEB trees rarely pay off, and O(N log N) is what you should implement.
10. Where LIS Shows Up in Practice
10.1 Patience diff
Git’s default diff uses the Myers algorithm, which computes a shortest edit script (closely related to LCS). git diff --patience instead matches lines that occur exactly once in both files and keeps the largest set of those matches that appear in the same order in both files. That set is an LIS over line positions, computed with patience sorting, which is where the name comes from. It often gives more readable diffs when large blocks of code change.
10.2 Whole-genome alignment (MUMmer)
The original MUMmer aligner (Delcher et al., 1999) finds maximal unique matches (MUMs) between two genomes, sorts them by position in the first genome, and then picks the longest set of matches whose positions in the second genome also increase. That chaining step is a variant of LIS (it also accounts for match lengths and overlaps), and it runs in O(k log k) for k matches. The number of matches can be large, so the O(N log N) algorithm matters.
10.3 Aligning long transcripts
The same anchor-chaining trick works for speech data. Suppose you need to line up a long ASR transcript (with word timestamps) against a reference text, for example to cut a long recording into training segments:
- Find words or short n-grams that occur exactly once in both texts. Each match is a pair
(position_in_hypothesis, position_in_reference). - Sort the pairs by hypothesis position and take the LIS of the reference positions. Misrecognized or repeated words that would cross other matches drop out.
- The surviving matches are reliable anchors. Align the short gaps between them with ordinary edit distance or forced alignment.
Speech alignment is monotonic (time only moves forward), which is exactly the “same order in both sequences” constraint LIS enforces. For the dense, frame-level version of monotonic alignment, see Dynamic Time Warping in acoustic pattern matching.
10.4 Streaming monotonicity checks
The tails array can be updated one element at a time, so you can track the LIS length of a growing stream in O(log N) per element:
import bisect
class StreamingLIS:
def __init__(self):
self.tails = []
def add(self, num):
"""Add number to stream and return the current LIS length"""
pos = bisect.bisect_left(self.tails, num)
if pos == len(self.tails):
self.tails.append(num)
else:
self.tails[pos] = num
return len(self.tails)
def reset(self):
"""Reset for new sequence"""
self.tails = []
s = StreamingLIS()
print([s.add(x) for x in [10, 12, 15, 11, 80, 85]]) # [1, 2, 3, 3, 4, 5]
The ratio “LIS length / window length” is a simple non-parametric measure of how monotonic a window of metrics is. Two caveats: an LIS is a subsequence, not a contiguous run, so a high score does not mean the values rose without interruption; and removing the oldest element from tails is not supported, so a sliding window needs a recompute per window or a different statistic (a trend filter or a moving average). For many independent sequences, the work parallelizes trivially, for example with multiprocessing.Pool().map(Solution().lengthOfLIS, sequences).
11. Performance
The asymptotic gap is large in practice. On N = 10,000 random integers with CPython 3.14 on a 2017 laptop CPU (Intel i5-7360U), the O(N^2) DP took about 3.6 s and the binary search version about 2 ms. Expect different absolute numbers on your machine; the ratio is the point.
12. Interview Pro Tips
- Recognize the pattern: “Longest”, “Increasing”, “Subsequence” → think LIS.
- Start with DP: Explain the O(N^2) solution first.
- Optimize: Move to binary search for O(N log N), and explain why
tailsstays sorted. - Variants: Be ready to adapt (decreasing, 2D, count, weighted).
- Reconstruction: Know how to print the actual sequence.
13. Summary
| Approach | Time | Space | Notes |
|---|---|---|---|
| DP | O(N^2) | O(N) | Simple, easy to extend (count, weights, divisibility) |
| Binary Search (tails) | O(N log N) | O(N) | Optimal in the comparison model; length plus reconstruction via parents |
| Fenwick / segment tree | O(N log N) | O(N) | Handles weighted and counting variants |
LIS starts as a standard DP exercise, turns into a greedy binary search, and connects to card games, order theory, diff tools, genome alignment and transcript alignment. Both main approaches are exact; the difference is only running time, and the O(N log N) version is the one to know cold.
FAQ
Why does the binary search approach maintain a sorted tails array?
The tails array stores the smallest possible tail element for each increasing subsequence length. When bisect_left finds a position to replace, the new value is smaller than or equal to the old value at that position but larger than the value at the previous position, maintaining sorted order. Appending only happens for values larger than all existing entries.
Is the tails array the actual longest increasing subsequence?
No. The tails array stores optimal tail values for each length, not the actual LIS elements. For input [2,5,3,7,1], tails ends as [1,3,7], which is not a subsequence at all because 1 comes last. To reconstruct an actual LIS, maintain a parent array tracking predecessors during each update.
How does patience sorting relate to LIS?
In the patience sorting card game, each card is placed on the leftmost pile whose top card is greater than or equal to the current card. If no such pile exists, a new pile is started. The number of piles formed equals the LIS length. Each pile is non-increasing in the order cards were placed, and the top cards form an increasing sequence corresponding to the tails array.
What is the Russian Doll Envelopes problem and how does it use LIS?
Given envelopes with width and height, find the maximum nesting depth. Sort by width ascending and height descending, then find the LIS of heights only. Sorting height in descending order within the same width prevents two envelopes with identical widths from appearing in the same subsequence, since their heights will be in decreasing order.