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:
- Sort the list.
- Loop over each number using index
i
. - Pick
j
to bei+1
, in other words, the leftmost number of the segment afteri
. - Pick
k
to ben-1
, in other words, the rightmost number of the segment afteri
. - 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.