Prove that this solution to the Closest 3-Sum problem always works

Question

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.

Answer 1

In the explanation, there is one bit missing: You will repeatedly find i, j, k such that a[i] + a[j] + a[k] ≥ target, and a[i] + a[j] + a[k-1] ≤ target. What's missing in the explanation is that for both cases you need to calculate the difference from the target, and keep track of the triple where the difference is smallest. Should you hit the target (by coincidence) then you're done.

Answer 2

The core of the problem is to solve the 2 sum closest problem for a particular i:

Given a target value, find a pair of numbers who's sum is closer to the target value.

The two pointer approach is the procedure you have described with j and k. (from now on called l and r for left and right)

Your question is why can we decrease r or increase l.

The answer is as the array is sorted, and suppose nums[r] + nums[l] < target, we would not gain any better result comparing nums[l] with any of the values of nums between l and r. Because for any other value in nums[l to r] the sum is even smaller. As we wouldn't get any better result, why not forget about the value nums[l] all together? Right? And that is what we do by increasing l.

This reasoning happens since the beginning of the 2 sum closest search. When l=0 and r=len(nums). We discard values one by one until we are left with l=r-1.