3sum - Leetcode Solution

The 3Sum problem on LeetCode is to find all unique triplets in the array which gives the sum of zero. In other words, the problem requires you to find three numbers from the array that sum up to zero.

The problem is quite popular and is considered a classic problem in computer science. The brute force approach to solve this problem would require three nested loops to check all possible triplets, which would take O(n^3) time complexity. Therefore, a more efficient solution should be used.

One way to solve this problem efficiently is by sorting the array first. Sorting the array would bring all the negative numbers to the left side of the array and all the positive numbers to the right side. The zero would end up in the middle.

Then, we can use a two-pointer approach to find the triplets. We start with fixing the first number and then look for the remaining two numbers whose sum adds up to the complement of the first number.

The two-pointer approach involves two pointers, one at the beginning and one at the end of the sorted array. We start by fixing the first number and then increment the left pointer if the sum of the first number and the left pointer element is less than the complement, or decrement the right pointer if the sum of the first number and the right pointer element is greater than the complement. If the sum is equal to the complement, we have found a triplet.

The code for the solution looks like this:

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

        for (int i = 0; i < n - 2; i++) {
            if (i == 0 || nums[i] != nums[i-1]) {
                int l = i + 1, r = n - 1;
                while (l < r) {
                    int sum = nums[i] + nums[l] + nums[r];
                    if (sum == 0) {
                        result.push_back({nums[i], nums[l], nums[r]});
                        while (l < r && nums[l] == nums[l+1]) l++;
                        while (l < r && nums[r] == nums[r-1]) r--;
                        l++;
                        r--;
                    } else if (sum < 0) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
        }
        return result;
    }
};

The above code has a time complexity of O(n^2) and space complexity of O(1) as we are not using any extra space.

The vector result stores all unique triplets that sum up to zero. We sort the input array nums to bring all negative numbers to the left side and positive numbers to the right side. Then, we iterate through the array using a for loop, fixing the first number and then using the two-pointer approach to find the other two numbers.

The if statement inside the for loop is used to skip any duplicate values. The while loop inside the two-pointer approach is used to skip any duplicate values. Finally, the return statement returns the vector result containing all unique triplets that sum up to zero.

1