0189HardArrayBinary SearchDynamic ProgrammingSortingLongest Increasing Subsequence

Nesting the Display Cases

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def deepest_case_nest(cases: list[list[int]]) -> int:

Java

public int deepestCaseNest(int[][] cases)

The intended approach

Time O(n log n)Space O(n)

Sorting by width turns the two-dimensional fit into a one-dimensional question about depths, but only if equal widths are handled: list them from deepest to shallowest so a later case of the same width can never extend a chain built on an earlier one. The answer is then the longest strictly rising run of depths in that order, tracked with a list of smallest chain-ending depths and a binary search that overwrites the first entry that is not smaller than the current depth.

Pythonentry point: deepest_case_nest

def deepest_case_nest(cases):
    # Order by width ascending, and by depth descending among equal widths so
    # that two cases of the same width can never both be picked. After that the
    # answer is the longest strictly increasing run of depths, which the usual
    # patience layout finds: tails[i] holds the smallest depth ending a run of
    # length i + 1, and each depth replaces the first tail not below it.
    # Time O(n log n). Space O(n).
    from bisect import bisect_left
    order = sorted(cases, key=lambda case: (case[0], -case[1]))
    tails = []
    for case in order:
        depth = case[1]
        slot = bisect_left(tails, depth)
        if slot == len(tails):
            tails.append(depth)
        else:
            tails[slot] = depth
    return len(tails)

The obvious version

Sort the cases, then fill a table where entry i is the deepest nest ending at case i, by scanning every earlier case and taking the best one that fits strictly inside. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_deepest_nest(cases):
    order = sorted(cases, key=lambda case: (case[0], case[1]))
    n = len(order)
    if n == 0:
        return 0
    best = [1] * n
    for i in range(n):
        for j in range(i):
            if order[j][0] < order[i][0] and order[j][1] < order[i][1]:
                if best[j] + 1 > best[i]:
                    best[i] = best[j] + 1
    return max(best)

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in