LIS / Patience
Quadratic DP over previous smaller elements, or keep the smallest tail for each length and binary search it for O(n log n).
Dynamic ProgrammingO(n log n) with tailsNew4 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
longest increasing subsequence
russian doll envelopes
max chain length
The template
Get this into muscle memory, then adapt the condition per problem.
const tails: number[] = [];
for (const x of nums) {
let i = lowerBound(tails, x);
if (i === tails.length) tails.push(x); else tails[i] = x;
}
return tails.length; Watch Longest Increasing SubsequenceIf you are stuck
The generic hint ladder for this pattern, in order.
- 1The subsequence is not contiguous, so windows do not apply.
- 2For each element, what is the best chain ending here?
- 3Storing minimal tails per length lets binary search replace the inner loop.
Drill it
Every problem in the bank that uses this pattern.
0 / 4 solved