Nesting Parcel Chain
Problem
A packaging line has flat parcels described by parcels[i] = [width, height]. Parcel A fits inside parcel B only if A's width is strictly smaller than B's width and A's height is strictly smaller than B's height. Parcels cannot be rotated.
Return the largest number of parcels you can nest one inside another in a single chain.
Example 1
- Input:
- parcels = [[5, 4], [6, 4], [6, 7], [2, 3]]
- Output:
- 3
[2, 3] → [5, 4] → [6, 7].
Example 2
- Input:
- parcels = [[1, 1], [1, 1], [1, 1]]
- Output:
- 1
Identical parcels cannot nest.
Constraints
- 1 ≤ parcels.length ≤ 10^5
- parcels[i].length == 2
- 1 ≤ width, height ≤ 10^5
Hint
Show the first hint
If parcels were sorted by width, you would need the longest strictly increasing sequence of heights.
Walkthrough
How to approach it
01Clarify before coding
- Can parcels rotate? No: width stays width.
- Both dimensions strictly smaller? Yes, equal width or equal height blocks nesting.
- n up to 10^5: the O(n²) pairwise DP is too slow.
02Brute force
Sort by width, then dp[i] = 1 + max(dp[j]) over j with smaller width and smaller height.
Cost: O(n²): about 5·10^9 pair checks at the limit.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.