Longest Increasing Subsequence with bisect
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A subsequence keeps the order but may skip items. The table solution compares every pair; a sorted tails list and binary search make it much faster.
The slow way: O(n squared)
A subsequence is a sequence taken from a list by deleting some items without changing the order of the rest. It does not need to be next to each other, unlike a substring.
A subsequence keeps the order of a list but may skip items. For daily marks, find the longest run of strictly rising marks. Let dp[i] be the longest one that ends at item i.
def lis(nums): dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp, default=0)
print(lis([5, 2, 8, 6, 3, 7, 9]))Example 1 · Slow table, printed
nums = [4, 10, 4, 3, 8, 9]dp = [1] * len(nums)for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1)print(dp)print(max(dp))[1, 2, 1, 1, 2, 3] 3
What this code does
dp[i]is the best run that ends at i, so the table is not always rising: it is 1, 2, 1, 1, 2, 3.- The best run is 4, 8, 9 or 3, 8, 9, length 3. The answer is
max(dp), notdp[-1].
Item i extends the best subsequence that ends at any smaller earlier item j. The answer is the largest cell, not the last. Time is O(n^2) and space is O(n), fine for n up to about 2000 in Python.
The fast way: a tails list
The tails list stores, for each length, the smallest possible last item of an increasing subsequence of that length. It stays sorted, so each new item is placed by binary search.
Keep a list tails, where tails[k] is the smallest last item of any rising subsequence of length k + 1. For each new mark, find the first tail that is not smaller and replace it. If none, add it at the end.
from bisect import bisect_left
def lis_fast(nums): tails = [] for x in nums: k = bisect_left(tails, x) if k == len(tails): tails.append(x) else: tails[k] = x return len(tails)
print(lis_fast([5, 2, 8, 6, 3, 7, 9]))Example 2 · Watch the tails list change
from bisect import bisect_left
tails = []for x in [5, 2, 8, 6, 3, 7, 9]: k = bisect_left(tails, x) if k == len(tails): tails.append(x) else: tails[k] = x print(x, tails)5 [5] 2 [2] 8 [2, 8] 6 [2, 6] 3 [2, 3] 7 [2, 3, 7] 9 [2, 3, 7, 9]
What this code does
- Replacing a tail with a smaller value keeps more room for later items. That is why tails keeps the smallest last item.
- The list at the end is [2, 3, 7, 9], but 2, 3, 7, 9 happens to also be a real run here. In general it may not be.
Example 3 · Fast against slow
from bisect import bisect_leftimport random
def slow(nums): dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp, default=0)
def fast(nums): tails = [] for x in nums: k = bisect_left(tails, x) if k == len(tails): tails.append(x) else: tails[k] = x return len(tails)
random.seed(7)same = 0for _ in range(200): nums = [random.randint(1, 20) for _ in range(random.randint(0, 15))] same += slow(nums) == fast(nums)print(same)200
What this code does
- Comparing the fast version with the slow one on 200 random lists is a good habit before trusting a trick.
- All 200 agree.
max(dp, default=0)handles the empty list.
tails is always sorted, so bisect_left finds the place by binary search in O(log n). Time is O(n log n) and space is O(n). The list is not itself a subsequence: only its length is the answer.
Strict or not strict
Strictly rising means equal marks do not count. Then replace the first tail that is greater than or equal to x, which is bisect_left. If equal marks are allowed, replace the first tail strictly greater, which is bisect_right.
from bisect import bisect_left, bisect_right
def longest(nums, strict=True): find = bisect_left if strict else bisect_right tails = [] for x in nums: k = find(tails, x) if k == len(tails): tails.append(x) else: tails[k] = x return len(tails)
print(longest([3, 3, 4, 4], True), longest([3, 3, 4, 4], False))Example 4 · Equal items allowed
from bisect import bisect_left, bisect_right
def longest(nums, strict): find = bisect_left if strict else bisect_right tails = [] for x in nums: k = find(tails, x) if k == len(tails): tails.append(x) else: tails[k] = x return len(tails)
marks = [2, 2, 3, 1, 3, 3]print(longest(marks, True))print(longest(marks, False))2 5
What this code does
- Strictly rising: 2, 3 or 1, 3 gives 2. Non-decreasing: 2, 2, 3, 3, 3 gives 5.
bisect_rightputs an equal value after the existing ones, so equal items build a longer run.
Example 5 · Items to remove
from bisect import bisect_left
def lis(nums): tails = [] for x in nums: k = bisect_left(tails, x) if k == len(tails): tails.append(x) else: tails[k] = x return len(tails)
scores = [10, 22, 9, 33, 21, 50, 41, 60]print(len(scores) - lis(scores))3
What this code does
- The fewest items to remove so the rest rises is the length minus the longest rising run.
- Here the run has length 5, so 3 items are removed.
One word changes the answer: for [3, 3, 4, 4] the strict answer is 2 and the non-decreasing answer is 4. Always read whether equal items are allowed.
Rebuilding one subsequence
The O(n^2) table can also give the subsequence itself. Keep, for each item, the index of the item before it, then walk back from the item with the largest dp.
def lis_items(nums): n = len(nums) dp, prev = [1] * n, [-1] * n for i in range(n): for j in range(i): if nums[j] < nums[i] and dp[j] + 1 > dp[i]: dp[i], prev[i] = dp[j] + 1, j i = dp.index(max(dp)) out = [] while i != -1: out.append(nums[i]) i = prev[i] return out[::-1]
print(lis_items([5, 2, 8, 6, 3, 7, 9]))Example 6 · The actual run
nums = [10, 22, 9, 33, 21, 50, 41, 60]n = len(nums)dp, prev = [1] * n, [-1] * nfor i in range(n): for j in range(i): if nums[j] < nums[i] and dp[j] + 1 > dp[i]: dp[i], prev[i] = dp[j] + 1, ji = dp.index(max(dp))out = []while i != -1: out.append(nums[i]) i = prev[i]print(out[::-1])[10, 22, 33, 50, 60]
What this code does
- The table remembers where each run came from, like the coins used in coin change.
- Two runs of length 5 exist; this walk finds the first one.
prev[i] is the item that comes just before i in its best run. The reversed walk gives the items in order. There can be several equally long answers; this one finds the first.
Next step
Check your understanding
11 quick questions