3 Sum – Finding Triplets with Target Sum in an Array
Finding Triplets 3 Sum – Medium Level Problem
Given an array of integers, nums, find all unique sets of three numbers [nums[i],nums[j],nums[k]] that add up to zero (nums[i]+nums[j]+nums[k]=0).
Make sure each number in a triplet has a different index, and the result should not include duplicate triplets. You can return the triplets in any order.
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].
Output: []
Explanation: The only possible triplet does not sum up to 0.
Output: [[0,0,0]]
Explanation:The only possible triplet sums up to 0.
Constraints:
- 3 <= nums.length <= 1000
- -10^5 <= nums[i] <= 10^5
Finding Triplets 3 Sum Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(n^2) time and O(1) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A straightforward solution is to check every possible triplet in the array, resulting in a time complexity of O(n^3). Can you come up with a more efficient approach?
Hint 2 :
Can you think of an algorithm that works after sorting the input array? What insights can we gain by rearranging the equation provided in the problem?
Hint 3 :
By iterating through the array with index i, we can rearrange the equation to -nums[i] = nums[j] + nums[k]. How can we efficiently find the pairs j and k without duplicates?
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Hash Map Method
- Two Pointers Method
1. Brute Force Method
This approach involves checking all possible triplets in the array using three nested loops, leading to a time complexity of O(n³). It’s simple but inefficient for larger datasets.
- Time complexity: O(n^3)
- Space complexity: O(m)
where m is the number of triplets and n is the length of the given array.
Code
class Solution {
public:
vector<vector <int>> threeSum(vector& nums) {
set<vector> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
for (int k = j + 1; k < nums.size(); k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
res.insert({nums[i], nums[j], nums[k]});
}
}
}
}
return vector<vector>(res.begin(), res.end());
}
};
public class Solution {
public List<List <Integer>> threeSum(int[] nums) {
Set<List> res = new HashSet<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
List tmp = Arrays.asList(nums[i], nums[j], nums[k]);
res.add(tmp);
}
}
}
}
return new ArrayList<>(res);
}
}
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = set()
nums.sort()
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
for k in range(j + 1, len(nums)):
if nums[i] + nums[j] + nums[k] == 0:
tmp = [nums[i], nums[j], nums[k]]
res.add(tuple(tmp))
return [list(i) for i in res]
class Solution {
/**
* @param {number[]} nums
* @return {number[][]}
*/
threeSum(nums) {
const res = new Set();
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) { if (nums[i] + nums[j] + nums[k] === 0) { res.add(JSON.stringify([nums[i], nums[j], nums[k]])); } } } } return Array.from(res).map(item => JSON.parse(item));
}
}
2. Hash Map Method
By iterating through the array and using a hash map to store previously seen elements, this approach reduces the problem to finding pairs that sum up to a target value. The time complexity is O(n²) due to the nested iteration over the array.
- Time complexity: O(n^2)
- Space complexity: O(n)
Code
class Solution {
public:
vector<vector <int>> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
vector<vector> res;
for (int i = 0; i < nums.size(); i++) { count[nums[i]]--; if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size(); j++) { count[nums[j]]--; if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int target = -(nums[i] + nums[j]);
if (count[target] > 0) {
res.push_back({nums[i], nums[j], target});
}
}
for (int j = i + 1; j < nums.size(); j++) {
count[nums[j]]++;
}
}
return res;
}
};
public class Solution {
public List<List <Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
List<List> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) { count.put(nums[i], count.get(nums[i]) - 1); if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length; j++) { count.put(nums[j], count.get(nums[j]) - 1); if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int target = -(nums[i] + nums[j]);
if (count.getOrDefault(target, 0) > 0) {
res.add(Arrays.asList(nums[i], nums[j], target));
}
}
for (int j = i + 1; j < nums.length; j++) {
count.put(nums[j], count.get(nums[j]) + 1);
}
}
return res;
}
}
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
count = defaultdict(int)
for num in nums:
count[num] += 1
res = []
for i in range(len(nums)):
count[nums[i]] -= 1
if i and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums)):
count[nums[j]] -= 1
if j - 1 > i and nums[j] == nums[j - 1]:
continue
target = -(nums[i] + nums[j])
if count[target] > 0:
res.append([nums[i], nums[j], target])
for j in range(i + 1, len(nums)):
count[nums[j]] += 1
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[][]}
*/
threeSum(nums) {
nums.sort((a, b) => a - b);
const count = new Map();
for (let num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
const res = [];
for (let i = 0; i < nums.length; i++) {
count.set(nums[i], count.get(nums[i]) - 1);
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < nums.length; j++) {
count.set(nums[j], count.get(nums[j]) - 1);
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
const target = -(nums[i] + nums[j]);
if (count.get(target) > 0) {
res.push([nums[i], nums[j], target]);
}
}
for (let j = i + 1; j < nums.length; j++) {
count.set(nums[j], count.get(nums[j]) + 1);
}
}
return res;
}
}
3. Two Pointers Method
After sorting the array, this method fixes one element and uses two pointers to find pairs that sum to a specific target. It has a time complexity of O(n²) and is more efficient than the brute force method.
- Time complexity: O(n^2)
- Space complexity: O(1) or O(n) depending on the sorting algorithm.
Code
class Solution {
public:
vector> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
vector> res;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = nums.size() - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum > 0) {
r--;
} else if (sum < 0) {
l++;
} else {
res.push_back({nums[i], nums[l], nums[r]});
l++;
r--;
while (l < r && nums[l] == nums[l - 1]) {
l++;
}
}
}
}
return res;
}
};
public class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = nums.length - 1;
while (l < r) {
int sum = nums[i] + nums[l] + nums[r];
if (sum > 0) {
r--;
} else if (sum < 0) {
l++;
} else {
res.add(Arrays.asList(nums[i], nums[l], nums[r]));
l++;
r--;
while (l < r && nums[l] == nums[l - 1]) {
l++;
}
}
}
}
return res;
}
}
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
if a > 0:
break
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res
class Solution {
/**
* @param {number[]} nums
* @return {number[][]}
*/
threeSum(nums) {
nums.sort((a, b) => a - b);
const res = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
let l = i + 1;
let r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (sum > 0) {
r--;
} else if (sum < 0) {
l++;
} else {
res.push([nums[i], nums[l], nums[r]]);
l++;
r--;
while (l < r && nums[l] === nums[l - 1]) {
l++;
}
}
}
}
return res;
}
}
