3Sum

Two pointers, Arrays

Problem Statement:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Problem Link: LeetCode

Approach:
We can take advantage of two pointers technique to solve this problem in effective way. Let’s fix a pointer i which will act a one valid member in the triplet. we have to find two more numbers to make the sum equal to 0.

Before moving to finding those two numbers, we have sort the array in ascending order to make the two pointer solution to work. Let’s take two pointers j = i + 1 and k = n — 1 Then, we calculate sum of these three numbers.

1. If it leads to zero, we’ll push these three triplets into the result array. Then move j and k pointer to next valid index. We don’t want to move the pointer to index where the number is same as previous value. So just move the pointers until we reach next new element.
2. If it’s greater then zero, which means we need to make the sum lower. So, let’s move the j pointer to j + 1
3. If it’s lesser then zero, which means we need to make the sum higher. So, let’s move the k pointer to k + 1
4. Repeat this process until i exceeds the length of the array.

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();

    vector<vector<int>> res;

    for(int i = 0; i < n; i++){
        if(i > 0 and nums[i] == nums[i - 1]){
            continue;
        }
        
        int l = i + 1, r = n - 1;

        while(l < r){
            int sum = nums[i] + nums[l] + nums[r];
            
            if(sum == 0){
                res.push_back({nums[i], nums[l], nums[r]});
                l++, r--;
                
                while(l < r and nums[l] == nums[l - 1]) l++;
                while(l < r and nums[r] == nums[r + 1]) r--;

                continue;
            }

            if(sum > 0){
                r--;
            }else{
                l++;
            }
        }

    }

    return res;

}

Time Complexity:
O(N log(N) * N) — where N is number of elements in the array.

Space Complexity:
O(N) — we are storing triplets in the result array.