I was working on a Leetcode problem, 3Sum Closest. I came up with a solution but struck it down because I didn't think it could be correct. But, turns out it was. I want to know why.

Here's the problem, transcribed:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

The top solution was basically this:

  1. Sort the list.
  2. Loop over each number using index i.
  3. Pick j to be i+1, in other words, the leftmost number of the segment after i.
  4. Pick k to be n-1, in other words, the rightmost number of the segment after i.
  5. If the sum of the numbers at (i, j, k) are less than the target, then j++. Otherwise, k--.

But isn't it possible that we might prematurely increment j (or decrement k), dismissing it forever, when in fact it may have been the optimal pairing had we tried a different k (or j)?

It seems we'll never backtrack to check other combinations.

Can someone provide a minimal, intuitive proof of why such a case never occurs? I'm unable to come up with a counterexample, and I trust the experienced members of Leetcode, so I know I must be wrong, but I can't seem to prove it. I can prove it for the Exact 3-Sum problem, but I don't know how to work with inequalities.

  • $\begingroup$ Also pay attention that you can aproach the target value from both left and right. $\endgroup$ – fade2black Oct 22 '17 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.