How should I practice Russian Doll Envelopes?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Russian Doll Envelopes associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Russian Doll Envelopes

Google● HardINTERNONSITE INTERVIEW

Learn

Problem statement

You are given an array envelopes, where envelopes[i] = [width, height] describes one envelope.

An envelope can be placed inside another only if both its width and its height are strictly smaller. Envelopes may not be rotated.

Return the maximum number of envelopes that can be nested inside one another.

Function

maxEnvelopes(envelopes: int[][]) → int

Examples

Example 1

envelopes = [[5,4],[6,4],[6,7],[2,3]]return = 3

The envelopes [2,3], [5,4], and [6,7] form a nesting chain of length 3.

Example 2

envelopes = [[1,1],[1,1],[1,1]]return = 1

Equal dimensions are not strictly smaller, so no two envelopes can be nested.

Constraints

1 <= envelopes.length <= 100000.
envelopes[i].length == 2.
1 <= envelopes[i][0], envelopes[i][1] <= 100000.