LC: 3Sum Smaller - spiralgo/algorithms GitHub Wiki

The Essence:

This problem can actually be reduce to a 2 sum problem:

Adding 3 numbers being less than some value is equivalent to picking one of these numbers, subtracting it from the target value and the sum of the other 2 being less than target - subtracted value (target_).
We can then sort the array, loop over it from from the lowest value to the largest, subtract the value from the target and look at the right rest of the array for pairs of suitable numbers.
We can then start this comparison from the right next of the value. The other compared value should then be the largest value. If some largest value + the left value is smaller than target_ then all the values smaller then this right large value can be added with the left value to get a sum smaller than target_.

The strategy of reducing problems to other problems that are easier to solve is ubiquitous strategy in problem solving and the problem-solvers should always keep this in their tool bag.

Details:

In implementation, there are a few more things to notice:

The right pointer must be always larger than the left pointer then.
If the previous operation is successful, we can increment the left pointer to look for two sums with the number at this pointer. Remember, the array is sorted.
We should then do this collect the possible two sum combinations each time until the loop condition is false.
In the main loop, if we can't find any two sums at some index, that means that we won't be able to find two sums for numbers larger than it for further indices.
We don't always need to initialize the right boundary with the size of the array. Since the numbers are always getting larger, our new first possible right pointer will either be smaller than or equal to the previous first possible. So, we can store that in a variable.

The implementations can be found here: https://github.com/spiralgo/algorithms/tree/master/src/main/java/algorithms/curated170/medium/threesumsmaller