Two shard sizes closest to a target
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
You are moving data onto a new node and want to pick two shards whose combined size is as close as possible to the space you have. sizes is sorted from smallest to largest.
Return the sum of two shards at different positions that is closest to target. If two sums are equally close, return the smaller one.
- 2 ≤ sizes.length ≤ 200,000
- sizes is sorted, non-decreasing
- 0 ≤ sizes[i], target ≤ 10⁹
Examples
closestPair([1, 3, 8, 12, 20], 15)returns153 + 12.closestPair([1, 2, 9, 10], 7)returns101 + 9 = 10 is 3 away; the next closest, 1 + 2 = 3 and 2 + 9 = 11, are 4 away.closestPair([4, 6], 100)returns10
Hints
Hint 1 of 2
Start with the smallest and the largest. If their sum is below the target, which of the two can never be part of a better pair?
Hint 2 of 2
Move the left pointer right when the sum is too small, the right pointer left otherwise, and keep the best sum seen, applying the tie rule.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Picture every pair as a cell in a grid, rows for the left shard and columns for the right. Checking every cell is quadratic. With the list sorted, one comparison rules out a whole row or column.
Take the smallest and largest. If their sum is below the target, the smallest shard is too small even with the largest partner, so every pair it is in is below target too, and no closer than this one. Move it right. If the sum is above target, the largest shard is too large even with the smallest partner; move it left.
Record the best sum before moving, and apply the tie rule there: equally close, keep the smaller sum. If a sum hits the target exactly, nothing can be closer.
function closestPair(sizes, target) {
let i = 0, j = sizes.length - 1, best = sizes[0] + sizes[1];
while (i < j) {
const sum = sizes[i] + sizes[j];
const d = Math.abs(sum - target), bd = Math.abs(best - target);
if (d < bd || (d === bd && sum < best)) best = sum;
if (sum < target) i++;
else if (sum > target) j--;
else return sum;
}
return best;
}Complexity. O(n) time, O(1) extra space.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.