FunctionRacerProblemsRace

Nesting Boxes

HardSorting and searchingPython, JavaScript, TypeScript, Java, C++

Each item of boxes is [width, height]. Box A can go inside box B only if A is strictly narrower and strictly shorter: widthA < widthB and heightA < heightB. Boxes cannot be rotated. A box can hold one box directly, which may itself hold another, and so on, forming a chain.

Return the largest number of boxes that can form one chain. A single box is a chain of length 1, and an empty list gives 0. Two boxes with the same width or the same height never nest, whichever way round.

Example 1

boxes [[5,4],[6,4],[6,7],[2,3]]
returns 3

[2, 3] fits in [5, 4], which fits in [6, 7]. [6, 4] cannot join: it is as tall as [5, 4] and as wide as [6, 7].

Example 2

boxes [[1,1],[1,1],[1,1]]
returns 1

Identical boxes never nest, so the longest chain is a single box.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Sorting and searching problems