Last updated on July 15th, 2024 at 12:32 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
Topics
Array, Two Pointers
Companies
Adobe, Amazon, Bloomberg, Facebook, Microsoft
Level of Question
Medium
Table of Contents
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
- Sorting: The input array num is sorted.
- Iterating: Iterate through each element of the array, treating each element num[i] as a potential first element of the triplet.
- Two-Pointer Approach: For each num[i], use two pointers (front and back) to find pairs that sum up to -num[i].
- Checking for Duplicates: Skip over duplicate elements to ensure unique triplets.
- 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(n2).
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
- Sorting: The input array nums is sorted.
- Iterating: Iterate through the array with a while loop to find the first element of the triplet.
- Two-Pointer Approach: For each element nums[i], use two pointers (j and k) to find pairs that sum up to zero.
- Checking for Duplicates: Skip over duplicate elements to ensure unique triplets.
- 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(n2).
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
- Sorting: The input array nums is sorted.
- Iterating: Iterate through the array with a for loop to find the first element of the triplet.
- Two-Pointer Approach: For each element nums[i], use two pointers (j and k) to find pairs that sum up to zero.
- Checking for Duplicates: Skip over duplicate elements to ensure unique triplets.
- 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(n2).
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
- Categorizing: Split the numbers into positive, negative, and zero.
- 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(n2).
4.3 Space Complexity
- O(n).