FastPrep
Problem · Array

Russian Doll Envelopes

Learn this problem
● HardInMobi logoInMobiFULLTIMEONSITE INTERVIEW

Problem statement

You are given a two-dimensional integer array envelopes, where envelopes[i] = [width_i, height_i] describes one envelope.

One envelope can fit inside another only when both its width and its height are strictly smaller than the other envelope's dimensions. Envelopes cannot 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

One maximum nesting chain is [2,3] -> [5,4] -> [6,7], which contains 3 envelopes.

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 <= 10^5
  • envelopes[i].length == 2
  • 1 <= width_i, height_i <= 10^5

More InMobi problems

drafts saved locally
public int maxEnvelopes(int[][] envelopes) {
    // Write your code here.
}
envelopes[[5,4],[6,4],[6,7],[2,3]]
expected3
checking account