Longest Chain of Nested Boxes
Updated
Problem statement
You have n boxes with no lid. Box i is boxes[i] = [width, height, length]. Every box stands upright, so its floor (the base) is width by length and its height points up. You may turn a box on its floor, which swaps width and length, but you may not tip it over.
Box a fits inside box b when both of these hold:
- The base of
ais strictly smaller than the base ofbon both sides. Compare the smaller base side ofawith the smaller base side ofb, and the larger with the larger. Both must be strictly smaller. - The height of
ais less than or equal to the height ofb.
A chain is a list of boxes where each box fits inside the next one. Return the largest number of boxes in one chain. A single box is a chain of 1.
Function
longestNestingChain(boxes: int[][]) → intExamples
Example 1
boxes = [[4,3,6],[2,2,3],[5,3,7],[3,4,4]]return = 3Write each box as (smaller base side, larger base side, height). Box 0 is (4, 6, 3), box 1 is (2, 3, 2), box 2 is (5, 7, 3) and box 3 is (3, 4, 4).
Box 1 fits in box 0: 2 < 4, 3 < 6 and height 2 <= 3. Box 0 fits in box 2: 4 < 5, 6 < 7 and height 3 <= 3, so equal heights are fine. That gives the chain 1, 0, 2 with 3 boxes.
Box 3 has height 4, which is taller than boxes 0 and 2, so it cannot go inside them, and nothing else fits inside it except box 1. No chain has 4 boxes, so the answer is 3.
Example 2
boxes = [[6,1,2],[3,1,5]]return = 1Box 1 has base sides 3 and 5. Box 0 has base sides 6 and 2. Turn box 0 so its sides are 2 and 6. Now 2 < 3 and 6 < 5 is false, so box 0 does not fit in box 1. Box 1 does not fit in box 0 either, because 3 < 2 is false. The answer is 1.
Example 3
boxes = [[5,9,5],[5,2,5],[8,10,8]]return = 2Boxes 0 and 1 have the same base, 5 by 5. A base must be strictly smaller on both sides, so neither fits in the other. Each of them fits in box 2 (5 < 8 on both sides, and heights 9 and 2 are at most 10). The longest chain is 2 boxes, such as box 1 inside box 2.
Constraints
1 <= boxes.length <= 1000boxes[i].length == 31 <= width, height, length <= 1000000
More Bloomberg LP Phone Screen questions
- N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Fewest Coins CombinationPHONE SCREEN · Seen Nov 2026
- Recommend Films from Viewers Who Watched Everything You DidPHONE SCREEN · Seen Nov 2026
- Track New Values in Sorted OrderPHONE SCREEN · Seen Nov 2026
- Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
- Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Match Shops and BuyersGoogle · PHONE SCREENGoogle interview questions
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Cheapest Order to Cut a RodAdobe · PHONE SCREENAdobe interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Maximum Length Pair ChainInMobi · ONSITE INTERVIEWInMobi interview questions
- Alternating Jumps to the Last IndexExpedia · OAExpedia interview questions
- Merge Overlapping IntervalsAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Merge Weekday and Time IntervalsNextdoor · PHONE SCREENNextdoor interview questions
- Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions
Bloomberg LP interview experiences
- Bloomberg SWE Phone Screen and Onsite: 1 Experience
- Bloomberg SWE Phone Screens with Two Teams: 1 Experience
- Bloomberg AI Interview, Hiring Level Not Reported: 2 Experiences
- Bloomberg Experienced SWE AI Coding Interviews: 2 Experiences
- Bloomberg New Grad AI-Assisted Coding Rounds: 3 Experiences
- Bloomberg New Grad SWE AI-Assisted Coding Rounds: 1 Experience