3 Sums and 3 Sums Closest

Let’s continue…

Problem Statement:

3 Sums

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution One: Brute force

The idea is simple. Create three loops, each loop iterate one specific element, and test the sum of elements from each combination. If the sum is equal to 0, we can consider to add them to the final vector list. Before we add it to the vector list, we still need to check whether it is already in the vector list. We can then iterate from the current vector list, and sort each sub arrays, and compare each sub array with current combination, if we find there are the same combination, we have to discard this combination.

Time Complexity: the worst case could be O(n^4), as the final vector list becomes larger, the check for getting rid of the same elements become more and more expensive.

Space Complexity: O(N), the worst case could be every three numbers can form a valid combination.

I will not provide the sample code here, for it is not hard to write code like this one. And it is so slow and can not pass the Leetcode test.

Solution Two:

Here is the reference for solution two: https://leetcode.com/problems/3sum/discuss/7380/Concise-O(N2

In general , the idea is like this: When we want to compare the sum of three elements, we can simply divide them into two parts. The first one is 0 – the first elements, and we save this as a result; then we find whether the sum of the rest two elements can equal to this result.

It seems like we still need at least O(n^3) time complexity to finish the task, but we can use some tricks to reduce the comparisons from the second part, and we can reduce the time complexity from O(n^2) to O(n). How?

The first thing we need to do is sort the original array, so this will take O(n*lgn) time complexity;

Then we can use two pointers to find the rest two elements, one pointer (lo) will point to the smallest element of the rest elements, another (hi) will point to the largest the element of the rest elements. For inner loop, we move these two pointers. Since all the rest elements are touched only once either by lo pointer or hi pointer, we can say the time complexity could be O(n).

OK, the next thing is how to get rid of the repetitive elements? Remember our array is sorted, which means we can safely move the pointer forward if we find the element[lo] == element[lo-1] (or element[hi – 1] == element[hi]). The pointer will stop until a different element is encountered.

Time Complexity: O(n), n is the number of elements in the array

Space Complexity: O(n)

https://gist.github.com/zhangxiaomu01/200b1db876e9e3381786ac8a8aa44c68

Problem Statement:

3 Sums Closest

Given array nums = [-1, 2, 1, -4], and target = 1.

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

Solution One: Brute force

The idea is similar to the last problem. We can use three loops and calculate the sum of the every three elements. We then subtract this sum with the target value, and calculate the absolute value of this subtraction. Basically, this is the distance between the sum and target value.

It’s not hard. I will provide the code.

Time Complexity: O(n^3)

Space Complexity: O(1)

Solution Two:

The same idea as the previous question (Solution two). First we find one element, and then using two pointers to find the other two elements. Note the only thing we need to change is how we calculate the bestSum.

Time Complexity: O(n^2)

Space Complexity: O(n)

That’s all for today. Thanks for reading.