Package Pair Sums
Problem
A delivery van has a remaining weight capacity cap. You are given the weights of the packages still on the dock and must choose exactly two of them so that their combined weight is as large as possible without exceeding cap. Return the indices of every pair that achieves that best total (there may be several). If no pair fits, return an empty list.
This is the first problem on the Amazon SDE online assessment for Egypt and MENA; it is graded on hidden tests including ties and duplicates.
Examples
Example 1
Input: weights = [10, 30, 25, 15, 20], cap = 45
Output: [[2, 4]] — 25 + 20 = 45 is the best total; 30 + 15 also equals 45, so the full answer is [[1, 3], [2, 4]]. Return both pairs.
Example 2
Input: weights = [50, 60], cap = 40
Output: [] — no two packages fit.
Constraints
- 2 ≤ n ≤ 10^5, 1 ≤ weight ≤ 10^6
- Indices in each pair ascending; pairs sorted by first index
- Target O(n log n); O(n²) will time out on the largest hidden test
What they look for
Sort with original indices attached, two pointers for the best sum, then a second pass (or a hash map) to collect every pair matching the best total. Handling the "many equal weights" case without blowing up to O(n²) output is the subtle part — say what you would do if the output itself is huge.