Loading page…
Practice problem · medium
A parcel-delivery app loads two parcels into one locker compartment. A compartment is only worth opening when the two parcels weigh more than a minimum load, which is the limit.
You want the lightest pair of parcels that is still above the limit, so the courier carries the least weight. You get the weights of the waiting parcels and the limit.
Write smallest_pair_sum_above(weights, limit).
weights[i] is the weight of the i-th parcel.i != j with weights[i] + weights[j] > limit.-1 when no pair is above the limit.Input: weights = [4, 9, 2, 7, 5], limit = 10
Output: 11The trace sorts the weights, then keeps one pointer at each end. The sum of the two ends tells which pointer to move.
| lo | hi | Sum | Above 10? | Best so far |
|---|---|---|---|---|
| 2 (0) | 9 (4) | 11 | yes | 11 |
| 2 (0) | 7 (3) | 9 | no: move lo | 11 |
| 4 (1) | 7 (3) | 11 | yes | 11 |
| 4 (1) | 5 (2) | 9 | no: move lo | 11 |
| 5 (2) | 5 (2) | - | pointers met: stop | 11 |
The sorted list is 2, 4, 5, 7, 9 and the positions in the table are sorted positions. The smallest sum above 10 is 11, so the output is 11.
Input: weights = [1, 2, 3], limit = 100
Output: -1The two heaviest parcels, 2 and 3, weigh 5, which is not above 100, so the output is -1.
Input: weights = [5, 5], limit = 9
Output: 10Two parcels of 5 weigh 10, which is above 9, so the output is 10.
0 ≤ weights.length ≤ 100,000 (waiting parcels)1 ≤ weights[i] ≤ 500,000,000 (weights in grams)0 ≤ limit ≤ 1,000,000,000Trying every pair costs about n × n / 2, which is about 5 × 10^9 at n = 100,000. Sorting costs n log n, about 1.7 million steps, and a two-pointer pass costs n more. A hash map does not help here, because the target is a range ("above the limit"), not one exact value.
smallest_pair_sum_above · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.