The problem
Each box is given as (width, height). A box fits inside another if its width and its height are both strictly smaller. Boxes cannot be turned. Return the largest number of boxes that can be put one inside the next, like a set of nesting dolls.
nest([(5, 4), (6, 4), (6, 7), (2, 3)]) # 3
# (2, 3) inside (5, 4) inside (6, 7)
nest([(3, 1), (3, 2), (3, 3)]) # 1
Limits
- Up to 100,000 boxes, with sides from 1 to 1,000,000. Comparing every pair (O(n²), n times n steps) is too slow; aim for O(n log n).
sortedandbisectare allowed.
Builds on DYNP-6 Longest increasing subsequence.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
10 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Same width | Not run | |
| 3 | Same height | Not run | |
| 4 | No boxes | Not run | |
| 5 | One box | Not run | |
| 6 | Equal boxes | Not run | |
| 7 | No turning | Not run | |
| 8 | Ten in a chain | Not run | |
| 9 | 100,000 boxes | Not run | |
| 10 | 100,000 boxes that all nest | Not run |