3Sum - Print unique Pairs

Problem Link - 3 Sum

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.

Another variant of the above problem just count the unique pairs.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Pre-req -2Sum

Approach -

• Here first we will fix the first element, and then check the remaining 2 elements using 2 Sum approach.

How to avoid duplicate triplets ?

• First we sort the array, so that all duplicates resides side by side.
• and next, we will do like for each position in the triplet(means 0th,1st,2nd), we will consider only the first occurence of the duplicates and skip the duplicates by checking if the curr element is equal to prev element arr[i]==arr[i-1]

Solution

• First, we will sort the entire array.
• We will use a loop(say i) that will run from 0 to n-1. This i will represent the fixed pointer. In each iteration, we will fix this value for all different values of the rest of the 2 pointers. Inside the loop, we will first check if the current and the previous element is the same and if it is we will do nothing and continue to the next value of i.
• there will be 2 moving pointers i.e. j(starts from i+1) and k(starts from the last index). The pointer j will move forward and the pointer k will move backward until they cross each other while the value of i will be fixed.
• Now we will check the sum i.e. arr[i]+arr[j]+arr[k].
• If the sum is greater, then we need lesser elements and so we will decrease the value of k(i.e. k--).
• If the sum is lesser than the target, we need a bigger value and so we will increase the value of j (i.e. j++).
• If the sum is equal to the target, we will simply insert the triplet i.e. arr[i], arr[j], arr[k] into our answer and move the pointers j and k skipping the duplicate elements(i.e. by checking the adjacent elements while moving the pointers).

Code

vector<vector<int>> triplet(int n, vector<int> &arr) {
    vector<vector<int>> ans;
    sort(arr.begin(), arr.end());
    for (int i = 0; i < n; i++) {
        //remove duplicates:
        if (i != 0 && arr[i] == arr[i - 1]) continue;

        //moving 2 pointers:
        int j = i + 1;
        int k = n - 1;
        while (j < k) {
            int sum = arr[i] + arr[j] + arr[k];
            if (sum < 0) {
                j++;
            }
            else if (sum > 0) {
                k--;
            }
            else {
                vector<int> temp = {arr[i], arr[j], arr[k]};
                ans.push_back(temp);
                j++;
                k--;
                //skip the duplicates:
                while (j < k && arr[j] == arr[j - 1]) j++;
                while (j < k && arr[k] == arr[k + 1]) k--;
            }
        }
    }
    return ans;
}

Time Complexity: O(NlogN)+O(N2), where N = size of the array.
Space Complexity: O(no. of quadruplets) - which is constant O(1), not using any extra space except for storing output