educative.io

Educative

Triplet Sum Close to Target - Explanation

Hello,

After some time spent on this if condition (lol) I think I finally found out how this works. Hopefully this helps understanding it…

I would say the trick for understanding this problem and provided solution is by imagining the number line. As we can see the, code is performing a subtraction to see for the distance between one point, targetSum, and another , which is the computed sum of a triplet, which in the code would be the part written as: -arr[i] - arr[left] - arr[right], By the way, instead of subtracting one by one lets just make it more explicit by creating the current triplet before using it in the subtraction:

int currentSum = arr[i] + arr[left] + arr[right];
int targetDiff = targetSum - currentSum;

Explanation for if statement with additional condition: || (Math.abs()targetDiff…
The way that made me understand this condition is that I used this case where we would obtain two differences with same numeric value but different in sign. So lets take this input:

arr = [-1, 0, 0, 1, 2, 4]
targetSum = 3

When computing the code for this, we will see an iteration where we have the triplet: [-1, 0, 0] this will make:
currentSum = -1 + 0 + 0 = -1
targetDiff = 3 - (-1) = 4
So imagine the number line:


  -1(cSum)       **3(targetS)**
          4 (tDiff)  

After this we will also have an iteration where we built the triplet: [1, 2, 4] which will make:
currentSum = 1, 2, 4 = 7
targetDiff = 3 - 7 = -4
number line:


                          **3(targetS)**          7(cSum)
                                        -4(tDiff)

The behavior you can notice is that when the currentSum is to the right of targetSum, the difference is obviously negative according to the order written in code for the subtraction. So we will fall in that second condition when we produced two currentSum’s that are equal in numeric value (for this case 4) but different in sign. And since the problem states that if there are more than 1 valid triplets we have to take the smallest, then in the code we will preserve the positive targetDiff cause graphically we see that it belongs to a target sum that fell to the left of our targetSum.

Explanation for last if-else statement:
Ok so this targetDiff result can be either negative, positive or 0. By basic maths we know targetDiff will be positive if currentSum (the subtrahend) is smaller than targetSum, so what do we need to do? increase currentSum, to get as closest as possible to 0 because that is when the triplets are the closest to targetSum, otherwise if the result is negative that means our currentSum is too big so we decrease currentSum.
Note until this point in the code, we wont receive a case when the targetDiff is 0 because that is taken care at the top. Since if we found the “perfect” triplet we just stop.

3 Likes

Hello @Joan_Piayet_Perez_Lo

Kudos to you for such a brief explanation! We really appreciate learners who deep dive and ponder over the provided solutions and explanations :slightly_smiling_face:.

1 Like