Startup VO Interview Coding Question: Maximum Number of Envelopes That Can Be Nested

49 Views
No Comments

Given a list of envelopes [width, height], find the maximum number of envelopes that can be nested inside each other.

An envelope can go inside another only if both its width and height are strictly smaller. Envelopes cannot be rotated.

The key idea is to sort envelopes by width ascending, and for equal widths, by height descending. This turns the 2D nesting condition into a longest increasing subsequence problem on heights. The descending tie-break is essential because envelopes with the same width cannot nest, and it prevents invalid chains. After sorting, apply an O(n log n) LIS algorithm to compute the maximum nesting count.

END
 0