Longest increasing subsequence — every question, written out
The longest chain of values that climbs left to right, skipping freely. Each element asks every smaller predecessor: can I extend you? Patience gets to n log n.
Read the longest increasing subsequence explanation and watch it run
Why is this LIS implementation O(n²)? Point at the work, not the loops.
Complexity derivation
Element i interrogates every earlier element, and summing i over all i gives n²/2 comparisons
The inner loop is not a fixed cost — it runs from 0 to i, so the eleventh element compares against ten predecessors and the last against nearly n. That triangular sum is n(n−1)/2, which is Θ(n²). Space stays O(n), for the dp lengths and the parent pointers.
See it run — One element, ten consecutive comparisons against every predecessor — the inner loop in full.
Follow-up: can you get the LENGTH of the LIS faster than O(n²)?
Complexity derivation
Yes — keep the smallest tail per chain length and binary-search it, giving O(n log n)
Maintain `tails[k]` = the smallest value that can end an increasing chain of length k+1; for each new value, binary-search for the first tail at least as large and overwrite it, appending when it beats them all. The array stays sorted, which is the loop invariant that makes the binary search legal, and its final length is the answer. Prism animates the table version because the table is what teaches the state-design lesson — the patience version is a different mental model with the same output.
Follow-up: your `tails` array is increasing and the right length. Is it the answer sequence?
Code diagnosis
No — its entries can come from incompatible chains, so it may not be a subsequence at all
Each slot in `tails` holds the best-so-far ending value for a chain of that length, and different slots can be updated by values from entirely different chains, at positions that do not increase. To recover the actual sequence you need parallel bookkeeping: record which slot each value landed in and a back-pointer to the previous slot’s occupant, then unwind from the last append. Saying this unprompted is a strong signal; claiming `tails` is the answer is a red flag.
How much extra memory does the table version need?
Complexity derivation
O(n) — one length per element, plus one parent index per element for the reconstruction
Two flat arrays are all this needs: `dp` for the lengths and `parent` for the predecessor indices. Dropping the parent array halves the memory and costs you the ability to report the sequence itself, which is the usual trade in this family. The quadratic cost is entirely in time, never in space.
Why is `dp[i]` defined as "ending at i" rather than "the best chain among the first i"?
Invariant identification
Because a future element needs the chain’s final value to know whether it may extend it
A subproblem summarised as "the best chain so far" has thrown away its last element, and without that value no later element can tell whether appending itself is legal. Anchoring the state to an endpoint keeps exactly the fact the transition needs, and turns extension into a single comparison. This is the transferable lesson: design the state around what the NEXT step must ask of it.
The sequence so far is 4, 8, 12, 16, then a drop, and now an 8 arrives. Which chain does the 8 extend?
Trace prediction
The chain ending at 4 — length 1 — because every longer chain ends at a value too big to follow
Two conditions apply and both are required: the predecessor must be strictly smaller, and among the legal ones you take the longest chain. Here 8, 12 and 16 are all disqualified by the first condition regardless of how long their chains are, leaving only the 4 and its chain of one — so dp becomes 2. Watching a length-4 chain sit uselessly next to a new element is the fastest cure for the greedy misreading.
See it run — The annotation reads "dp[5] = 2 (extends a[0] = 4)" — not the chain of four beside it.
Once the table is filled, where is the answer?
Invariant identification
The maximum over the whole dp array — the best chain ends somewhere, but not necessarily last
Every chain ends at exactly one index, and dp records the best chain ending at each — so the longest chain overall is the largest entry anywhere in the array. The parent pointers then turn that index back into the actual sequence. Reading `dp[n−1]` is a common slip and gives the right answer only when the last element happens to be the winner.
The table holds lengths. How do you get the actual subsequence back out?
Trade-off & selection
Record the predecessor index whenever dp[i] improves, then follow those parents back from the argmax and reverse
One extra integer per element — the index this chain came from — is enough to rebuild the sequence, because the chain is a linked list running backwards through the array. Start at the index holding the maximum dp, follow parents until one is absent, then reverse. Prism does exactly this at the end of the run and washes the winning elements through the skyline.
See it run — The reconstruction wash begins: parents followed back from the winner, marked one at a time.
Why can a sliding window solve "longest increasing SUBARRAY" but not "longest increasing SUBSEQUENCE"?
Comparison
A window can only represent contiguous elements, and a subsequence is allowed to skip
A window is defined by two endpoints, so the moment you are permitted to drop a middle element it can no longer describe the candidate. The subarray version really is a single linear scan that restarts on every decrease; the subsequence version needs a table because any earlier element remains a possible predecessor forever. The two problem names differ by one word and by a whole algorithm.
The interviewer changes "increasing" to "non-decreasing". What changes in your code?
Edge case reasoning
The predecessor test becomes `a[j] <= a[i]`; in the patience version it becomes an upper bound
On duplicate-free input the two answers are identical, so the change only bites where equal values exist — which is exactly where interviewers flip it, to see whether the comparison was understood or copied. In the table it is one character. In the patience version, lower bound becomes upper bound, and getting that backwards silently returns the strict answer.
What does the algorithm do on a strictly decreasing sequence?
Edge case reasoning
Every dp entry stays 1 and the answer is 1, after doing the full quadratic amount of work
Every comparison fails, every dp stays at its initial 1, and the answer is 1 — but the cost is still n(n−1)/2 comparisons, because nothing detects that the situation is hopeless. This is the same indifference merge sort has to sorted input: a fixed loop structure charges full price regardless. Reversed input is also the worst case for the patience variant, where every value overwrites `tails[0]`.
Someone initialises `dp` to zeros instead of ones. What do they see?
Code diagnosis
Every answer comes out one too small, and a single-element input returns 0
The 1 encodes "this element is a chain of itself", which is the base case of the whole recurrence; zeroing it means every chain forgets to count its own endpoint. The bug is uniform, so a test comparing against a known answer catches it instantly and a test comparing two buggy implementations never will. Any DP whose base case encodes a real fact deserves a comment saying which fact.
Envelopes nest if both width and height are strictly larger. How does LIS solve the longest nesting chain?
Trade-off & selection
Sort by width ascending with height descending on ties, then run LIS on the heights
Sorting by width enforces one dimension positionally, so the LIS over heights only has to enforce the other. The descending tie-break is what makes it correct: among equal widths only one envelope may be chosen, and a descending height order guarantees no increasing subsequence picks two of them. This reduction — impose one constraint by sorting, the other by LIS — is the pattern worth carrying to other two-key problems.
Explain the LIS table to someone who does not code. Say it out loud before revealing.
Explain it plainly
Imagine a row of people of different heights, and you want the longest run of people, reading left to right, where everyone is taller than the one before — but you are allowed to skip anybody you like. Here is the trick: walk down the line and ask each person one question. "Looking only at the people to your left who are shorter than you, which of them is standing at the end of the longest run so far?" They join that run, and their own answer is that run plus one. Everyone writes their number on a card and holds it up, so the next person can read it off without doing any work again. At the end, the biggest number anyone is holding is the answer, and you can walk backwards from that person, following who they joined, to recover the actual line. The part everyone gets wrong is the phrase "shorter than you". Suppose someone very tall stands early on holding a big number — a run of four. A shorter person later cannot join it, no matter how impressive the number is, because they would break the climb. They have to settle for a shorter run that ends below them. Where the picture breaks down: asking every person about everybody to their left is a lot of asking, and for a very long line there is a cleverer bookkeeping trick that avoids it — but it stops looking like people holding cards.
The listener should end up understanding why each element records its own chain rather than the best chain seen. A strong answer makes the trap concrete with a number, not with vocabulary.