Show problems as
Classic problem #354HardArrayBinary SearchDynamic ProgrammingSortingLongest Increasing Subsequence

Russian Doll Envelopes

Real-world version: Nesting the Display Cases
Tracked in this browser only
Read Russian Doll Envelopes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A museum stores glass display cases of many sizes. Case i is given as cases[i] = [width, depth].

One case slides inside another only when it is strictly narrower and strictly shallower than that case; matching either measurement is enough to jam it. Cases may be nested one inside the next as many levels deep as the sizes allow, and a case is never turned on its side, so width is always compared against width and depth against depth.

Return the greatest number of cases that can sit in a single nest, counting the outermost case.

Examples

Example 1

Input
cases = [[8, 6], [3, 4], [8, 9], [4, 8]]
Output
3

The case measuring 3 by 4 slides into the one measuring 4 by 8, which slides into the one measuring 8 by 9, so three cases share a nest.

Example 2

Input
cases = [[7, 7], [7, 7]]
Output
1

Two cases of identical size jam against each other, so a nest holds only one of them.

Example 3

Input
cases = [[2, 10], [10, 2]]
Output
1

The narrow case is deeper and the wide case is shallower, so neither one fits inside the other.

Constraints

  • 1 <= cases.length <= 10^5
  • cases[i].length == 2
  • 1 <= width, depth <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def deepest_case_nest(cases: list[list[int]]) -> int:
Java
public int deepestCaseNest(int[][] cases)

More on the same topics