Problem Explanation:

Given an array of integers, the task is to find all unique triplets in the array whose sum is zero. A triplet is just a combination of three numbers.

For example, given the array nums = [-1, 0, 1, 2, -1, -4], the solution would be: [ -1, 0, 1], [-1, -1, 2]

Note that the numbers in each triplet are in non-descending order and their sum is zero. Furthermore, the output shouldn't have any duplicate triplets.

Approach:

The basic idea is to iterate over the array, and for each element, treat it as the first element of a possible triplet. Then we use a two-pointer technique to find all combinations of triplets using the remaining elements in the array.

Here is how it works:

First, we sort the input array. Sorting is necessary because we want to skip over duplicate values.

Second, we iterate over the sorted array and use each value as the first number of the triplet. The rest of the array following this number is then divided into a left and right section using two pointers.

The left pointer starts from the number next to the chosen first number, and the right pointer starts from the last number of the array.

We calculate the sum of the numbers pointed by the two pointers along with the first number. If the sum equals zero, we have a triplet and add it to the result, then we move both pointers one step towards the middle.

If the sum is less than zero, we move the left pointer one step to the right. If the sum is larger than zero, we move the right pointer one step to the left. This is because we want to increase/decrease the sum to find more correct triplets.

Finally, we skip duplicate values for the first, second and third numbers in each triplet as we iterate through the array.

Walkthrough Example:

Let's take nums = [-1, 0, 1, 2, -1, -4] as an example.

After sorting, the array becomes [-4, -1, -1, 0, 1, 2].

We iterate over the array, taking -4 as the first number in the first iteration. Next, we use two pointers to check the potential combinations with -4. Initially, the left pointer points to -1, and the right pointer points to 2. The sum = -4 + -1 + 2 = -3 < 0. So we move the left pointer one step to the right. Now, the left pointer points to the next -1, and the right pointer remains at 2. The sum = -4 + -1 + 2 = -3 < 0. We move the left pointer one step to the right again. Then left pointer is at 0, and the sum = -4 + 0 + 2 = -2 < 0. We continue moving the left pointer until sum >= 0 or left pointer >= right pointer.

Finally, the sum = -4 + 1 + 2 = -1 < 0, the left pointer moves to the right, and the left pointer is now at 2, which equals the right pointer, indicating we've exhausted all combinations for -4.

Then we choose the next number -1 as the first number in the triplet and use the two pointers to check the remaining elements of the array. We continue this process until we've examined all possible unique triplets.

Solution Example:

For the given example nums = [-1, 0, 1, 2, -1, -4], the solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

Python Solution

1
2python
3class Solution:
4    def threeSum(self, nums):
5        res = []
6        nums.sort()
7        for i in range(len(nums)-2):
8            if i > 0 and nums[i] == nums[i-1]:
9                continue
10            l, r = i+1, len(nums)-1
11            while l < r:
12                s = nums[i] + nums[l] + nums[r]
13                if s < 0:
14                    l +=1 
15                elif s > 0:
16                    r -= 1
17                else:
18                    res.append((nums[i], nums[l], nums[r]))
19                    while l < r and nums[l] == nums[l+1]:
20                        l += 1
21                    while l < r and nums[r] == nums[r-1]:
22                        r -= 1
23                    l += 1; r -= 1
24        return res

Java Solution

1
2java
3import java.util.Arrays;
4import java.util.LinkedList;
5import java.util.List;
6
7public class Solution {
8    public List<List<Integer>> threeSum(int[] nums) {
9        Arrays.sort(nums);
10        List<List<Integer>> res = new LinkedList<>(); 
11        for (int i = 0; i < nums.length-2; i++) {
12            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
13                int lo = i+1, hi = nums.length-1, sum = 0 - nums[i];
14                while (lo < hi) {
15                    if (nums[lo] + nums[hi] == sum) {
16                        res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
17                        while (lo < hi && nums[lo] == nums[lo+1]) lo++;
18                        while (lo < hi && nums[hi] == nums[hi-1]) hi--;
19                        lo++; hi--;
20                    } else if (nums[lo] + nums[hi] < sum) lo++;
21                    else hi--;
22               }
23            }
24        }
25        return res;
26    }
27}

JavaScript Solution

1
2javascript
3var threeSum = function(nums) {
4    let res = []
5    
6    // if nums length < 3, it's impossible to get any triplets
7    if (nums.length < 3)
8        return res
9    
10    nums.sort((a,b) => a - b)
11    let n = nums.length
12    
13    for (let i = 0; i < n-2; i++) {
14        // skip duplicated numbers
15        if (i !== 0 && nums[i] === nums[i-1])
16            continue
17        
18        let left = i+1, 
19            right = n-1,
20            target = -nums[i]
21
22        while (left < right) {
23            let sum = nums[left] + nums[right]
24            if (sum === target) {
25                res.push([nums[i], nums[left], nums[right]])
26                // skip the same 'second number' & 'third number' of a triplet
27                while (left < right && nums[left] === nums[left+1])
28                    left++
29                while (left < right && nums[right] === nums[right-1])
30                    right--
31                left++
32                right--
33            } else if (sum < target) {
34                left++
35            } else {
36                right--
37            }
38        }
39    }
40    return res;
41};

C++ Solution

1
2c++
3class Solution {
4    public:
5    vector<vector<int>> threeSum(vector<int>& nums) {
6        vector<vector<int>> ans;
7        sort(nums.begin(), nums.end());
8        for (int i = 0; i < nums.size(); i++) {
9            int target = -nums[i];
10            int front = i + 1;
11            int back = nums.size() - 1;
12
13            while (front < back) {
14
15                int sum = nums[front] + nums[back];
16
17                // Finding answer which start from number nums[i]
18                if (sum < target)
19                    front++;
20
21                else if (sum > target)
22                    back--;
23
24                else {
25                    vector<int> triplet{nums[i], nums[front], nums[back]};
26                    ans.push_back(triplet);
27
28                    // Processing duplicates of Number 2
29                    while (front < back && nums[front] == triplet[1]) front++;
30
31                    // Processing duplicates of Number 3
32                    while (front < back && nums[back] == triplet[2]) back--;
33                }
34
35            }
36
37            // Processing duplicates of Number 1
38            while (i + 1 < nums.size() && nums[i + 1] == nums[i])
39                i++;
40
41        }
42        return ans;
43    } 
44};

C# Solution

1
2csharp
3public class Solution {
4    public IList<IList<int>> ThreeSum(int[] nums) {  
5        IList<IList<int>> res=new List<IList<int>>();
6        Array.Sort(nums);
7        for(int i=0;i<nums.Length;i++) {
8            int target=-nums[i];
9            int start=i+1;
10            int end=nums.Length-1; 
11            while(start<end) {
12                int sum=nums[start]+nums[end];
13                if(sum==target) {
14                    res.Add(new List<int>() {nums[i],nums[start],nums[end]});
15                    while(start<end && nums[start]==nums[start+1]) start++;
16                    while(start<end && nums[end]==nums[end-1]) end--;
17                    start++;
18                    end--;
19                }else if(sum>target)
20                    end--;
21                else
22                    start++;
23            }
24            while(i+1<nums.Length && nums[i+1]==nums[i]) i++;
25        }
26        return res;
27    }
28}

Time Complexity Analysis:

The first step involves iterating over the array, which has a time complexity of O(n). Next, when we iterate over the remaining elements of the array, for each element, we may have to move the left and right pointers from one end of the array to the other, which again takes O(n) time. Thus, for every element, we perform O(n) operation. Therefore, the overall time complexity is O(n^2).

Space Complexity Analysis:

For each triplet, we add it to the list of results. In the worst case, the given array might have all identical elements, and thus all unique triplets would be identical. In such case, we only add one triplet to the results.

However, if all numbers are distinct, the number of valid triplets can be of the order n^3. But for the purpose of analysis, we usually don't consider the space required for the output result.

Apart from that, we are not using any additional data structure that grows with input size. Therefore, the overall space complexity is O(1), which signifies that our algorithm uses constant extra space.

Conclusion:

In this article, we have discussed a comprehensive approach on how to find all unique triplets in the given array whose sum equals zero. The problem has been solved using multiple programming languages like Python, Java, JavaScript, C++, and C#. The process involves sorting the array and using two pointers to find possible combinations of triplets. The time complexity is O(n^2) and the space complexity is O(1). Please note that this problem is a perfect example of how two pointer technique can be utilized to solve tricky problems efficiently.