hardCodingMidSeniorStaff
Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?
Russian doll envelopes reduce to a longest increasing subsequence. Sort by width ascending, break width ties by height descending, then run the O(n log n) tails search on heights. The descending tie-break stops equal widths from chaining, since a strictly increasing run then takes at most one per width.
4 min readUpdated 2026-10-10
Answer
Short answer
Russian doll envelopes are a longest increasing subsequence in disguise. Sort the envelopes by width ascending and, when widths are equal, by height descending. Then the answer is the longest strictly increasing subsequence of the heights, found in O(n log n) with the tails array. The descending tie-break is what stops two envelopes of the same width from being counted as nested.
Was this answer helpful?
Likely follow-ups
- Envelopes may nest when width and height are greater than or equal. Which two lines change?
- Widths must strictly increase but equal heights are allowed. Does any tie-break order still work?
- Boxes have length, width and height and may not be rotated. What is your approach now?
- Return the envelopes in nesting order, from the smallest outwards.
Related questions
- Find the length of the longest strictly increasing subsequence, then get it under quadratic time.hardAlso on dynamic-programming and longest-increasing-subsequence6 min
- Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?mediumAlso on dynamic-programming5 min
- Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D daysmediumAlso on binary-search5 min
- Sorting a list throws IllegalArgumentException saying the comparison method violates its general contract. What did the comparator get wrong?mediumAlso on sorting5 min