Two order sizes closest to a target

Question

You want to combine two orders whose sizes add up as close as possible to a target notional T. Given a list of sizes, return the pair whose sum is nearest to T (in absolute difference).

sizes = [1, 3, 4, 7], T = 6
-> (1, 4)          # sum 5 is 1 away; ties resolved by first found

The sums 1 + 4 = 5 and 3 + 4 = 7 are each 1 away from 6; this solution returns the first one it encounters, (1, 4).

Return a pair (x, y) minimizing |x + y - T|. Aim for $O(n \log n)$ .

Accepted Answer

Sort the sizes and converge two pointers from the ends. Track the best pair by absolute distance to T. If the current sum is below T, moving the left pointer up increases the sum toward the target; if above, moving the right pointer down decreases it. An exact hit ends the search early. Tracing [1, 3, 4, 7] with T = 6: the ends 1 + 7 = 8 are 2 away; shrinking the right pointer gives 1 + 4 = 5, only 1 away, which is recorded first and never beaten, so the answer is (1, 4). Time O(n \log n) from the sort, space O(1) beyond it. The monotonic pointer moves rely on sorting; each step provably cann…

Two order sizes closest to a target

Your answer

More Coding questions