What is the simple dynamic programming solution?

Let dp[i] be the length of the longest increasing subsequence ending at i. Set it to 1 plus the maximum dp[j] over earlier j with nums[j] < nums[i]. This is O(n^2) time and O(n) space.

How does the O(n log n) method work?

Keep a tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1. For each number, binary search for its position and overwrite it, or append if it is larger than all.

Does the tails array contain the actual subsequence?

No. It holds the best tails for each length, not a valid subsequence, so only its length equals the answer. To recover the sequence, store predecessor indices as well.

Should I use bisect_left or bisect_right?

Use bisect_left for a strictly increasing subsequence, so equal values replace the existing tail. Use bisect_right for non-decreasing.

What is the difference between a subsequence and a substring?

A subsequence keeps order but may skip elements; a substring must be contiguous. Mixing them up leads to the wrong problem.

What are the edge cases?

An empty array returns 0, a single element returns 1, a fully decreasing array returns 1, and an all-equal array returns 1 for the strict version.

Longest increasing subsequence, twice

Q: How does the O(n log n) method work?

Keep a tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1. For each number, binary search for its position and overwrite it, or append if it is larger than all.

Q: Does the tails array contain the actual subsequence?

No. It holds the best tails for each length, not a valid subsequence, so only its length equals the answer. To recover the sequence, store predecessor indices as well.

Q: Should I use bisect_left or bisect_right?

Use bisect_left for a strictly increasing subsequence, so equal values replace the existing tail. Use bisect_right for non-decreasing.

Q: What is the difference between a subsequence and a substring?

A subsequence keeps order but may skip elements; a substring must be contiguous. Mixing them up leads to the wrong problem.

Q: What are the edge cases?

An empty array returns 0, a single element returns 1, a fully decreasing array returns 1, and an all-equal array returns 1 for the strict version.

Interview QuestionsBy Ashish JangraUpdated 25 October 2026

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

Speed

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."

import bisect 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 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)

import bisect 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 is_subsequence(sub, a): it = iter(a) return all(any(x == y for y in it) for x in sub) 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) print(f" input {case}") print(f" tails {t} -> a valid subsequence of the input? {is_subsequence(t, case)}")

import bisect 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)) def is_subsequence(sub, a): it = iter(a) return all(any(x == y for y in it) for x in sub) for case in ([10, 9, 2, 5, 3, 7, 101, 18], [2, 6, 8, 3, 4, 5, 1]): seq = lis_with_sequence(case) print(f" input {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.")

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 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(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")

import bisect 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 # 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("input", flat) print(" strictly increasing (bisect_left) :", lis_nlogn(flat)[0]) print(" non-decreasing (bisect_right):", lis_non_decreasing(flat))

About the author

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.

Longest increasing subsequence, twice

Step through it

What to watch

Say this out loud

Overview

Run it

The quadratic version first

What the tails array actually holds

The trap: tails is not the answer

Strict, non-strict, and the follow-ups

Edge cases to raise

Sources and next steps

How the code works

How the code works

Change one thing

Where this runs

Check yourself