Nested boxes
The longest chain of boxes where each fits inside the next. About 15 minutes.
What order makes it a familiar problem?
To nest one box inside another, both the width and the height must be strictly smaller. Thinking about two sizes at once is awkward. What if you first line the boxes up by width, smallest first? Then any box can only fit inside boxes that come after it, and the width is taken care of.
What is left is a question about heights alone, in a known order. Does that remind you of anything from the subsequences stage?
The smallest box, 2 by 3, has nothing before it that fits inside: a chain of 1.
Can a 5 by 4 box nest inside a 6 by 4 box?
- ANo
- BYes, because 5 is less than 6
- CYes, if you turn the box on its side
Show the answer
No. Both sizes must be strictly smaller. The heights are equal, so it doesn't fit.
Nested boxes
You are given boxes, where boxes[i] is [width, height]. One box can be placed inside another only if both its width and its height are strictly smaller. Boxes cannot be turned. Return the largest number of boxes that can be nested one inside the next, like Russian dolls.
boxes = [[5, 4], [6, 4], [6, 7], [2, 3]] → 3
0 ≤ boxes ≤ 500 · 1 ≤ width, height ≤ 10,000