Hello and welcome back brave human being,

Before we delve into the problem, I want to hear, how is your interview process going? How are holding up?

Great things take time, be patient.

This problem is going to be the last one of two pointers and DAMN does this problem make your head spin.

Day 9: 15. 3Sum

This problem is a bit harder than our usual two-pointer problem. A naive solution would be to do three nested loops and calculate all of the possible combinations, which would result in a time complexity of O(n³).

Let’s think a bit deeper, how can we make it faster? Leverage two-pointers?

YAAASS! 💅 

The general idea is to fixate a third pointer with an outer loop and then apply the two-pointer technique.

The first step would be to … sort!

Once sorted, we are going to have an outer loop that iterates through the array until the second to last element (array.size()-2), and in our inner loop, we are going to use the two-pointer technique.

At each step of the algorithm, we are going to calculate if the sum of the three pointers is equal to 0.

If it is greater than 0; R—;

If it is less than 0; L++;

class Solution {
public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end()); 
        std::vector<std::vector<int>> ans; 
        int n = nums.size();

        for (int i = 0; i < n - 2; ++i) {
            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return ans; 
    }
};

Now, if you did the problem (which I know you did). You’ll notice that you need to handle duplicates BEFORE you add Memory complexity by adding a hashmap. Is there something you can leverage?

The array is … sorted!

So you can add some tweaks to our solution:

Handle duplicates in our outer loop:

Handle duplicates in our Left and Right pointer:

 if (sum == 0) {
                    ans.push_back({nums[i], nums[left], nums[right]});
                    // Skip duplicates
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }

And voila! You get a solution in O(n²), with no extra memory.

Here is a visual example:

In the end, it is not about how many problems you solve, it is about how many patterns you can detect and apply.

Come back on Monday to learn a new pattern.

Have a great weekend!

Denisse