Last updated on October 10th, 2024 at 12:47 am

Here, We see 3Sum LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

List of all LeetCode Solution

3Sum LeetCode Solution

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.

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.

1. 3Sum Leetcode Solution C++

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > result;
        std::sort(num.begin(), num.end());
        for (int i = 0; i < num.size(); i++) {
            int target = -num[i];
            int front = i + 1;
            int back = num.size() - 1;

            while (front < back) {
                int sum = num[front] + num[back];
                // Finding answer which start from number num[i]
                if (sum < target)
                    front++;
                else if (sum > target)
                    back--;
                else {
                    vector<int> triplet = {num[i], num[front], num[back]};
                    result.push_back(triplet);
        
                    // Processing duplicates of Number 2
                    // Rolling the front pointer to the next different number forwards
                    while (front < back && num[front] == triplet[1]) front++;
                    // Processing duplicates of Number 3
                    // Rolling the back pointer to the next different number backwards
                    while (front < back && num[back] == triplet[2]) back--;
                }    
            }
            // Processing duplicates of Number 1
            while (i + 1 < num.size() && num[i + 1] == num[i]) 
                i++;
        }
        return result;
    }
};

1.1 Explanation

1. Sorting: The input array num is sorted.
2. Iterating: Iterate through each element of the array, treating each element num[i] as a potential first element of the triplet.
3. Two-Pointer Approach: For each num[i], use two pointers (front and back) to find pairs that sum up to -num[i].
4. Checking for Duplicates: Skip over duplicate elements to ensure unique triplets.
5. Adding Triplets: When a valid triplet is found, add it to the result and move the pointers to skip duplicates.

1.2 Time Complexity

• O(n²).

1.3 Space Complexity

• O(n).

2. 3Sum Leetcode Solution Java

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length < 3) return result;
        Arrays.sort(nums);
        int i = 0;
        while(i < nums.length - 2) {
            if(nums[i] > 0) break;
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0) result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                if(sum <= 0) while(nums[j] == nums[++j] && j < k);
                if(sum >= 0) while(nums[k--] == nums[k] && j < k);
            }
            while(nums[i] == nums[++i] && i < nums.length - 2);
        }
        return result;
    }
}

2.1 Explanation

1. Sorting: The input array nums is sorted.
2. Iterating: Iterate through the array with a while loop to find the first element of the triplet.
3. Two-Pointer Approach: For each element nums[i], use two pointers (j and k) to find pairs that sum up to zero.
4. Checking for Duplicates: Skip over duplicate elements to ensure unique triplets.
5. Adding Triplets: When a valid triplet is found, add it to the result and move the pointers to skip duplicates.

2.2 Time Complexity

• O(n²).

2.3 Space Complexity

• O(n).

3. 3Sum Leetcode Solution JavaScript

var threeSum = function(nums) {
	var result = [];
	if (nums.length < 3) {
		return result;
	}
	nums = nums.sort(function(a, b) {
		return a - b;
	});
	for (var i = 0; i < nums.length - 2; i++) {
		if (nums[i] > 0) {
			return result;
		}
		if (i > 0 && nums[i] == nums[i - 1]) {
			continue;
		}
		for (var j = i + 1, k = nums.length - 1; j < k;) {
			if (nums[i] + nums[j] + nums[k] === 0) {
				result.push([nums[i], nums[j], nums[k]]);
				j++;
				k--;
				while (j < k && nums[j] == nums[j - 1]) {
					j++;
				}
				while (j < k && nums[k] == nums[k + 1]) {
					k--;
				}
			} else if (nums[i] + nums[j] + nums[k] > 0) {
				k--;
			} else {
				j++;
			}
		}
	}
	return result;
};

3.1 Explanation

1. Sorting: The input array nums is sorted.
2. Iterating: Iterate through the array with a for loop to find the first element of the triplet.
3. Two-Pointer Approach: For each element nums[i], use two pointers (j and k) to find pairs that sum up to zero.
4. Checking for Duplicates: Skip over duplicate elements to ensure unique triplets.
5. Adding Triplets: When a valid triplet is found, add it to the result and move the pointers to skip duplicates.

3.2 Time Complexity

• O(n²).

3.3 Space Complexity

• O(n).

4. 3Sum Leetcode Solution Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = set([])
        plus = sorted([n for n in nums if n>0])
        plus_c = set(plus)
        zero = [n for n in nums if n == 0]
        minus = sorted([n for n in nums if n<0])
        minus_c = set(minus)
        # all zero
        if len(zero)>2:
            ans.add((0,0,0))
        # plus zero minus
        if len(zero)>0:
            for n in minus:
                if -n in plus_c:
                    ans.add((n,0,-n))
        # plus minus minus
        n = len(minus)
        for i in range(n):
            for j in range(i+1,n):
                diff = -(minus[i]+minus[j])
                if diff in plus_c:
                    ans.add((minus[i],minus[j],diff))
        # plus plus minus
        n = len(plus)
        for i in range(n):
            for j in range(i+1,n):
                diff = -(plus[i]+plus[j])
                if diff in minus_c:
                    ans.add((diff,plus[i],plus[j]))
        return list(ans)

4.1 Explanation

1. Categorizing: Split the numbers into positive, negative, and zero.
2. Checking Triplets:
   • All zeros: If there are at least three zeros, add (0, 0, 0) to the result.
   • Plus-zero-minus: For each negative number, check if its positive counterpart exists in the positive set.
   • Plus-minus-minus: For each pair of negative numbers, check if the positive counterpart exists in the positive set.
   • Plus-plus-minus: For each pair of positive numbers, check if the negative counterpart exists in the negative set.

4.2 Time Complexity

• O(n²).

4.3 Space Complexity

• O(n).