Skip to interview prep
Apexed

388. In a circus tower each person must be both shorter and lighter than the person below. Given heights and weights, what is the tallest tower? (The same as Russian-doll envelopes.)

MediumDynamic programming

Technical
Show model answer

This is a 2D longest increasing subsequence. Sort by height ascending, and for equal heights sort by weight descending, so two people with the same height can never both appear in an increasing run. Then find the strict LIS on weights with the O(n log n) tails method. Total O(n log n) time and O(n) space.

The O(n²) DP over pairs (`best[i] = 1 + max(best[j])` where person j is strictly smaller in both) also works and is easier to get right first. Forgetting the descending tie-break is the classic bug: it lets equal-height people stack.

In a circus tower each person must be both shorter and lighter than the person below. Given heights and weights, what is the tallest tower? (The same as Russian