[Algorithms] 10 - 3Sum

Link to the problem

Three sum problem uses some ideas from two sum problem. But this problem is way harder to come up with the valid solution than two sum, thus, very different question. In this post I am going to go over what makes this problem so hard to solve and the solution as well.

Why this is harder than two sum?

Using hash map or set would not be efficient enough to catch duplicates. In two sum problem, all we needed to do was to push visited elements to the set and if the element was visited, ignore it.

But for three sum, we need to store an array for each number to make sure the combination of numbers are unique or not. This is very hard to implement and inefficient when it comes to time complexity as well.

Solution

So what would be the valid approach to the solution? The first key is using sorting technique to remove all duplicates so that we don't make same combination.

For example, if the array looks like

[1,-3,5,4,-3,2,2,-3,4,-3]

and if we sort it, we get

[-3,-3,-3,-3,1,2,2,4,4,5]

Therefore, we can skip the duplicated numbers after we find the valid combination that makes the sum 0 by sorting the array.

The second key is using two pointers method to search for the right number. We can increase the low pointer when the sum is less than zero, and decrease the high pointer when the sum is bigger than zero unless the two pointers pointing to the same element.

The problem is a little bit tricky to implement in the code.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>res;

        // Sort the array first. This is for removing duplicates & two pointer search.
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++)
        {

            if(i > 0 && nums[i] == nums[i-1])continue;

            int low = i +1;
            int high = nums.size() - 1;

            while(low < high)
            {
                int sum = nums[low] + nums[high] + nums[i];
                if(sum < 0) low++;
                else if(sum > 0) high--;
                else{
                    vector<int> tmp = {nums[low], nums[high], nums[i]};
                    res.push_back(tmp);
                    low++;
                    while(nums[low] == nums[low-1] && low < high)low++;
                }
            }
        }

        return res;
    }
};

As you can see, we are skipping elements if they have the same values.

if(i > 0 && nums[i] == nums[i-1])continue;

while(nums[low] == nums[low-1] && low < high)low++;

Time complexity analysis

The time complexity of the solution is O(n^2) because we are using two pointers method. I was confused about it at first, because I thought I was using binary search for the problem. But since we are moving low and high one by one for each loop, the solution will have O(n^2) instead of O(nlogn)