The quadratic version is the honest first answer: best[i] is the longest run ending at i, found by looking back at every earlier element. The O(n log n) version keeps a tails array where tails[k] is the smallest tail of any increasing run of length k+1, and binary searches it. Its length is the answer — its contents are not the subsequence.
Overview
The question, and what it is testing
The quadratic version is the honest first answer: best[i] is the longest run ending at i, found by looking back at every earlier element. The O(n log n) version keeps a tails array where tails[k] is the smallest tail of any increasing run of length k+1, and binary searches it. Its length is the answer — its contents are not the subsequence.
Dynamic programmingCoding problemMedium
Step through it
What to watch
tails stays sorted, which is what licenses the binary search.
A replacement never changes the length — it lowers a tail so it is easier to extend.
The final tails contents are not a valid subsequence.
Say this out loud
"The O(n squared) version: best[i] is the length of the longest increasing run ending at i, computed by scanning everything before i. For O(n log n) I keep an array where position k holds the smallest possible tail of a run of length k+1 - it stays sorted, so each element is placed with a binary search: extend the array if it beats every tail, otherwise overwrite the first tail that is not smaller. The length of that array is the answer. If I need the actual subsequence I keep predecessor pointers, because the tails array is not it."
Longest increasing subsequence, twice
Find the length of the longest strictly increasing subsequence. Can you do better than O(n squared)?
Run it
Both versions, agreeing on the length.
1Python
import bisect, random, time
def lis_quadratic(a):
"""best[i] = longest increasing run ENDING at i."""
if not a:
return 0, 0
best = [1] * len(a)
comparisons = 0
for i in range(len(a)):
for j in range(i):
comparisons += 1
if a[j] < a[i] and best[j] + 1 > best[i]:
best[i] = best[j] + 1
return max(best), comparisons
def lis_nlogn(a):
"""tails[k] = smallest possible tail of an increasing run of length k+1."""
tails = []
for x in a:
i = bisect.bisect_left(tails, x) # bisect_right for non-decreasing
if i == len(tails):
tails.append(x) # extends the longest run
else:
tails[i] = x # lowers a tail; length unchanged
return len(tails), tails
def lis_with_sequence(a):
"""The same algorithm, keeping predecessors so the run can be rebuilt."""
tails, tail_idx, prev = [], [], [-1] * len(a)
for i, x in enumerate(a):
k = bisect.bisect_left(tails, x)
if k == len(tails):
tails.append(x); tail_idx.append(i)
else:
tails[k] = x; tail_idx[k] = i
prev[i] = tail_idx[k - 1] if k > 0 else -1
out, cur = [], tail_idx[-1]
while cur != -1:
out.append(a[cur]); cur = prev[cur]
return list(reversed(out))
demo = [10, 9, 2, 5, 3, 7, 101, 18]
q, comps = lis_quadratic(demo)
n, tails = lis_nlogn(demo)
print("input:", demo)
print(f" quadratic: {q} ({comps} comparisons)")
print(f" n log n : {n} tails = {tails}")
print(" agree on the length:", q == n)
Output
Whether tails is the subsequence - checked on two inputs rather than claimed on one.
2Python
import bisect, random, time
def lis_quadratic(a):
if not a:
return 0, 0
best = [1] * len(a)
comparisons = 0
for i in range(len(a)):
for j in range(i):
comparisons += 1
if a[j] < a[i] and best[j] + 1 > best[i]:
best[i] = best[j] + 1
return max(best), comparisons
def lis_nlogn(a):
tails = []
for x in a:
i = bisect.bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails), tails
def lis_with_sequence(a):
tails, tail_idx, prev = [], [], [-1] * len(a)
for i, x in enumerate(a):
k = bisect.bisect_left(tails, x)
if k == len(tails):
tails.append(x); tail_idx.append(i)
else:
tails[k] = x; tail_idx[k] = i
prev[i] = tail_idx[k - 1] if k > 0 else -1
out, cur = [], tail_idx[-1]
while cur != -1:
out.append(a[cur]); cur = prev[cur]
return list(reversed(out))
demo = [10, 9, 2, 5, 3, 7, 101, 18]
def is_subsequence(sub, a):
it = iter(a)
return all(any(x == y for y in it) for x in sub)
print()
print("tails is not, in general, the subsequence. Checked rather than claimed:")
for case in ([10, 9, 2, 5, 3, 7, 101, 18], [2, 6, 8, 3, 4, 5, 1]):
_, t = lis_nlogn(case)
seq = lis_with_sequence(case)
print(f" input {case}")
print(f" tails {t} -> a valid subsequence of the input? {is_subsequence(t, case)}")
print(f" rebuilt {seq} -> valid? {is_subsequence(seq, case)}")
print(" on the second input the 1 is the LAST element, so it cannot precede")
print(" the 3 - the length is right and the contents are not the answer.")
Output
The cost that separates them, and the one call that changes the question.
3Python
import bisect, random, time
def lis_quadratic(a):
if not a:
return 0, 0
best = [1] * len(a)
comparisons = 0
for i in range(len(a)):
for j in range(i):
comparisons += 1
if a[j] < a[i] and best[j] + 1 > best[i]:
best[i] = best[j] + 1
return max(best), comparisons
def lis_nlogn(a):
tails = []
for x in a:
i = bisect.bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails), tails
def lis_with_sequence(a):
tails, tail_idx, prev = [], [], [-1] * len(a)
for i, x in enumerate(a):
k = bisect.bisect_left(tails, x)
if k == len(tails):
tails.append(x); tail_idx.append(i)
else:
tails[k] = x; tail_idx[k] = i
prev[i] = tail_idx[k - 1] if k > 0 else -1
out, cur = [], tail_idx[-1]
while cur != -1:
out.append(a[cur]); cur = prev[cur]
return list(reversed(out))
demo = [10, 9, 2, 5, 3, 7, 101, 18]
random.seed(5)
big = [random.randint(0, 10**6) for _ in range(1_200)]
t0 = time.perf_counter(); a1, c1 = lis_quadratic(big); x = time.perf_counter() - t0
t0 = time.perf_counter(); a2, _ = lis_nlogn(big); y = time.perf_counter() - t0
print()
print(f"n = {len(big)}")
print(f" quadratic {x*1000:7.1f} ms ({c1:,} comparisons) -> {a1}")
print(f" n log n {y*1000:7.1f} ms -> {a2}")
print(f" agree: {a1 == a2} speed-up {x/y:.0f}x")
# Strict against non-decreasing: one function call.
flat = [1, 3, 3, 3, 5]
def lis_non_decreasing(a):
tails = []
for x in a:
i = bisect.bisect_right(tails, x)
if i == len(tails): tails.append(x)
else: tails[i] = x
return len(tails)
print()
print("input", flat)
print(" strictly increasing (bisect_left) :", lis_nlogn(flat)[0])
print(" non-decreasing (bisect_right):", lis_non_decreasing(flat))
Output
The quadratic version first
best[i] = the length of the longest increasing subsequence ending at index i. To compute it, look at every j < i with a[j] < a[i] and take the best of those, plus one. The answer is the maximum over all best[i].
It is O(n²), it is four lines, and it is the right thing to write first. The "ending at i" framing is the part worth saying aloud: without it people try to define best[i] as "the answer for the first i elements", which does not admit a recurrence, because you cannot tell whether the run can be extended.
What the tails array actually holds
This is the part that is usually recited without being understood. tails[k] is the smallest value that can end an increasing subsequence of length k+1, among everything seen so far.
Two facts follow. It is sorted, because a longer run must end higher than the best ending of a shorter one — which is what makes the binary search legal. And overwriting an entry never breaks anything: replacing a tail with a smaller value keeps the same achievable length while making future extensions easier.
So each element does one of two things. If it exceeds every tail, it extends the longest run and the array grows. Otherwise it replaces the first tail that is not smaller than it — bisect_left — and the length is unchanged.
The trap: tails is not the answer
Run it on [2, 6, 8, 3, 4, 5, 1] and the final tails array is [1, 3, 4, 5]. The length, 4, is correct. The contents are not a subsequence of the input at all — the 1 is the last element, so it cannot precede the 3. The real answer is [2, 3, 4, 5].
What makes this trap dangerous is that tails often is a valid subsequence by coincidence: on [10, 9, 2, 5, 3, 7, 101, 18] it comes out as [2, 3, 7, 18], which is genuinely increasing and genuinely a subsequence. Checking one example proves nothing here. If the actual subsequence is wanted, keep a predecessor index for each element as it is placed and walk the chain backwards — the editor below does that, and checks both against the input rather than asserting.
Strict, non-strict, and the follow-ups
bisect_left gives strictly increasing: an equal value replaces rather than extends. bisect_right gives non-decreasing, where equal values extend the run. One function call, two different problems — and the problem statement often does not say which it wants.
The name to know is patience sorting, after the card game: each tail is the top card of a pile, and you place each new card on the leftmost pile whose top is not smaller. The number of piles is the answer. It is also the basis of the difflib patience diff, which is a good thing to be able to mention.
What to say out loud
The O(n squared) version: best[i] is the length of the longest increasing run ending at i, computed by scanning everything before i. For O(n log n) I keep an array where position k holds the smallest possible tail of a run of length k+1 - it stays sorted, so each element is placed with a binary search: extend the array if it beats every tail, otherwise overwrite the first tail that is not smaller. The length of that array is the answer. If I need the actual subsequence I keep predecessor pointers, because the tails array is not it.
Edge cases to raise
Volunteering these is most of what separates a correct answer from a good one.
Empty input. Length 0, and the quadratic version's max(best) raises on an empty list.
All equal values. Strictly increasing gives 1, non-decreasing gives n. Which one the problem wants is frequently unstated.
Strictly decreasing input. The answer is 1 and the tails array is length 1, overwritten every step - the case worth tracing if the replacement logic looks suspicious.
The follow-ups interviewers ask
"Return the subsequence, not the length." Keep a predecessor index per element and walk it backwards. It has to be said explicitly because the tails array is not the answer - the editor checks both against the input.
"Longest non-decreasing instead."bisect_right rather than bisect_left. One call, and on [1,3,3,3,5] the answer changes from 3 to 5.
"What is patience sorting?" This algorithm, named after the card game: each tail is the top card of a pile and each new card goes on the leftmost pile whose top is not smaller. The number of piles is the answer, and it is also the basis of patience diff.
Common wrong answers
"The tails array is the subsequence." The single most common error. On [2,6,8,3,4,5,1] tails ends as [1,3,4,5], and the 1 is the last element of the input - so it is not a subsequence at all.
"Sort the array and find the longest common subsequence." O(n2) at best and it is a much harder algorithm for the same answer. It is a real technique and the wrong tool here.
"best[i] is the answer for the first i elements." That does not admit a recurrence, because you cannot tell whether the run can be extended. It has to be 'ending at i'.
Recap in one screen
tails stays sorted, which is what licenses the binary search.
A replacement never changes the length - it lowers a tail so it is easier to extend.
The final tails contents are not a valid subsequence.
Worth trying: Print tails after every element of [2, 6, 8, 3, 4, 5, 1] and watch the final 1 overwrite the 2. That single step is where the array stops being a subsequence of the input.
Worth trying: Swap bisect_left for bisect_right and re-run on [1, 3, 3, 3, 5]. One call, and the answer changes from 3 to 5.
How the code works
Both versions agreeing, the comparison count and timing that separate them, and the predecessor chain that recovers the actual subsequence the tails array does not give you.
How the code works
best = [1] * len(a)Every element is an increasing run of length 1 on its own, which is the base case. The quadratic version is worth writing first because it makes the recurrence obvious.
i = bisect.bisect_left(tails, x)The binary search is legal only because tails is sorted — and it is sorted because a longer run must end higher than the best ending of a shorter one.
tails[i] = xA replacement, not an extension. The length is unchanged; what improves is how easy that length is to extend next time.
prev[i] = tail_idx[k - 1] if k > 0 else -1The predecessor chain, which is what actually recovers the subsequence. Without it you have the length and nothing else.
Change one thing
Print tails after every element of [2, 6, 8, 3, 4, 5, 1] and watch the final 1 overwrite the 2. That single step is where the array stops being a subsequence of the input.
Swap bisect_left for bisect_right and re-run on [1, 3, 3, 3, 5]. One call, and the answer changes from 3 to 5.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 4
Answer without scrolling back up.
In the quadratic version, what does best[i] mean?
"Ending at i" is what admits a recurrence - you need to know what the run ends with to know whether it can be extended.
What does tails[k] hold?
Which is why it stays sorted, and why replacing an entry with a smaller value never loses anything.
Is the final tails array the longest increasing subsequence?
On [10,9,2,5,3,7,101,18] tails ends as [2,3,7,18], but 18 comes after 101 in the input. Recovering the real run needs predecessor pointers.
How do you switch from strictly increasing to non-decreasing?
bisect_left makes an equal value replace; bisect_right makes it extend. One call, two problems.
Cheat sheet
Longest increasing subsequence, twice
The quadratic version is the honest first answer: best[i] is the longest run ending at i, found by looking back at every earlier element. The O(n log n) version keeps a tails array where tails[k] is the smallest tail of any increasing run of length k+1, and binary searches it. Its length is the answer — its contents are not the subsequence.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.