Two shard sizes closest to a target

MediumAbout 25 minProblem 2 of 2 in Two pointersDraft

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

  1. closestPair([1, 3, 8, 12, 20], 15)returns 153 + 12.
  2. closestPair([1, 2, 9, 10], 7)returns 101 + 9 = 10 is 3 away; the next closest, 1 + 2 = 3 and 2 + 9 = 11, are 4 away.
  3. closestPair([4, 6], 100)returns 10

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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open