All problems

Russian Doll Envelopes

Hard · dynamic programming

A stationery shop has a pile of flat envelopes. Envelope i is envelopes[i][0] wide and envelopes[i][1] tall.

One envelope can be slipped inside another only when it is strictly narrower and strictly shorter than the other one. Envelopes cannot be turned round, so a width is always compared with a width and a height with a height.

Pick envelopes and nest them one inside the next, like a set of Russian dolls. Return the largest number of envelopes you can nest in a single chain. Each envelope can be used at most once, and the envelopes in the list are in no particular order.

Examples

Example 1

Input: envelopes = [[4, 5], [6, 7], [6, 3], [2, 2]]

Output: 3

Nest [2, 2] inside [4, 5], and [4, 5] inside [6, 7]. The envelope [6, 3] is not tall enough to hold [4, 5].

Example 2

Input: envelopes = [[3, 3], [3, 5], [3, 9]]

Output: 1

All three have the same width, and equal widths do not count as strictly narrower, so no envelope fits in another.

Example 3

Input: envelopes = [[1, 4], [2, 3], [3, 2], [4, 1]]

Output: 1

Each envelope is wider than the one before it but shorter, so none fits inside another.

Constraints