progress

~/problems / 1-D dynamic programming / Longest increasing subsequence

Nesting boxes: turning, 3-D and one box per box

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard assessment 4 levels ~60 min

Level 1 The longest nest

A storeroom keeps flat cardboard boxes. Each box is [w, h]: a width and a height, both positive integers. Box A goes inside box B only when A is strictly smaller in both dimensions (A.w < B.w and A.h < B.h). Boxes keep the orientation they are listed in: a width is always compared with a width.

A nest is a run of boxes where each one goes inside the next. Write max_nest(boxes) -> int: how many boxes the longest nest holds, counting the outer one. With no boxes the answer is 0.

max_nest([[100, 100], [20, 80], [39, 39]])
# 2: [20,80] or [39,39] fits in [100,100], but neither fits in the other

max_nest([[100, 100], [39, 39], [20, 80], [29, 29], [19, 79], [10, 10]])
# 4: [10,10] in [29,29] in [39,39] in [100,100]
#    ([10,10] in [19,79] in [20,80] in [100,100] is another nest of 4)

max_nest([[5, 5], [5, 7], [5, 9]])
# 1: equal widths never nest

Constraints: 0 <= len(boxes) <= 100_000, 1 <= w, h <= 10^9. The same box may be listed more than once. You may reorder or modify boxes.

⭐ Bonus: a speed test with 100,000 boxes earns a star in O(n log n). Comparing every pair of boxes, O(n²), passes every other test but not this one.

Show hint

once the boxes are sorted by width, only the heights matter. Boxes with the same width are the trap: think about how to order them so that you can never pick two of them.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Level 4 unlocks when level 3 passes.

Topic: Longest increasing subsequence. O(n log n) with tails[] + bisect; rebuild via parent pointers.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc