In this post, we are going to solve the 15. 3Sum problem of Leetcode. This problem 15. 3Sum is a Leetcode medium level problem. Let’s see code, 15. 3Sum.

Problem

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.

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.

Constraints

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105

Now, let’s see the code of 15. 3Sum – Leetcode Solution.

3Sum – Leetcode Solution

15. 3Sum – Solution in Java

class Solution {
    public List<List<Integer>> threeSum(int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (arr[i] > 0) break; // Since arr[i] <= arr[l] <= arr[r], if a[i] > 0 then sum=arr[i]+arr[l]+arr[r] > 0
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = arr[i] + arr[l] + arr[r];
                if (sum < 0) l++;
                else if (sum > 0) r--;
                else {
                    ans.add(Arrays.asList(arr[i], arr[l], arr[r]));
                    while (l+1 <= r && arr[l] == arr[l+1]) l++; // Skip duplicate nums[l]
                    l++;
                    r--;
                }
            }
            while (i+1 < n && arr[i+1] == arr[i]) i++; // Skip duplicate nums[i]
        }
        return ans;
    }
}

15. 3Sum – Solution in C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin() , nums.end());     
        if(nums.size() < 3){               
            return {};
        }
        if(nums[0] > 0){                   
            return {};
        }
        unordered_map<int , int> hashMap;
        for(int i = 0 ; i < nums.size() ; ++i){    
            hashMap[nums[i]] = i;
        }
        vector<vector<int>> answer;
        for(int i = 0 ; i < nums.size() - 2 ; ++i){ 
            if(nums[i] > 0){    
                break;
            }
            for(int j = i + 1 ; j < nums.size() - 1 ; ++j){    
                int required = -1*(nums[i] + nums[j]);   
                if(hashMap.count(required) && hashMap.find(required)->second > j){ 
                    answer.push_back({nums[i] , nums[j] , required});
                }
                j = hashMap.find(nums[j])->second; 
            }
            i = hashMap.find(nums[i])->second;     
        }
        return answer; 
    }
};

15. 3Sum – Solution in Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] > 0: break  # Since arr[i] <= arr[l] <= arr[r], if arr[i] > 0 then sum=arr[i]+arr[l]+arr[r] > 0
            l = i + 1
            r = n - 1
            while l < r:
                sum3 = nums[i] + nums[l] + nums[r]
                if sum3 == 0:
                    ans.append([nums[i], nums[l], nums[r]])
                    while l+1 < n and nums[l+1] == nums[l]: l += 1  # Skip duplicates nums[l]
                    l += 1
                    r -= 1
                elif sum3 < 0: l += 1
                else: r -= 1
                
            while i+1 < n and nums[i+1] == nums[i]: i += 1  # Skip duplicates nums[i]
            i += 1
        return ans

Note: This problem 15. 3Sum is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.