Solving “Three Sum” in JS
Today we will be solving the LeetCode Three Sum problem in JavaScript. The Three Sum problem on LeetCode is a variation of the Two Sum problem, with the added constraint that we must find all unique triplets in an array that add up to a specific target. The problem statement is as follows:
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
There are several ways to solve this problem, but in this article, we will explore three different solutions:
Brute force solution
Using a hash table
Two Pointer Technique
- Brute Force Solution
The brute force solution is the most straightforward approach to solving this problem. We can simply iterate through the array and compare every possible triplet of elements to see if they add up to the target value. This can be done by using nested loops. The outermost loop iterates through the array, the middle loop starts from the outer loop’s current index +1 and continues till the end of the array, and the innermost loop starts from the middle loop’s current index +1 and continues till the end of the array. For every triplet of elements being checked, if the sum is equal to the target, we add it to the result array.
function threeSum(nums, target) {
let result = [];
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] === target) {
result.push([nums[i], nums[j], nums[k]]);
}
}
}
}
return result;
}This solution has a time complexity of O(n³) which is not efficient for large arrays, because for an array of size n, we need to check nnn triplets of elements.
Get nathan brickett’s stories in your inbox
Join Medium for free to get updates from this writer.
2. Using a hash table
Another approach is to use a hash table to store the elements as we iterate through the array. For each element, we check if the pair (the target minus the current element) is already in the hash table. If it is, we have found the two elements that add up to the target value.
function threeSum(nums, target) {
let result = [];
const hash = {};
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
const complement = target - (nums[i] + nums[j]);
if (complement in hash) {
result.push([nums[i], nums[j], complement]);
} else {
hash[nums[j]] = true;
}
}
}
return result;
}This solution has a time complexity of O(n²) which is more efficient than the brute force solution. We iterate over the array once, and for each element, we check all the other possible pairs with a time complexity of O(n) and check if it’s complement is in the hash table which is a constant time operation.
3. Two Pointer Technique
Another approach is to use the two pointer technique. The idea is to sort the array first, and then use two pointers, one starting from the beginning and one from the end, to find the triplets that add up to the target value. This approach has a time complexity of O(n²) and doesn’t take up extra space.
function threeSum(nums, target) {
let result = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === target) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}This solution uses the two pointer technique and also sorts the array first. It also skips the duplicate elements in the outer loop and inner loop. This way we can find all the triplets that add up to the target value without repetition.
In conclusion, the brute force solution is the most straightforward approach, but it is not the most efficient for large arrays. Using a hash table or two pointers is a more efficient solution, with a time complexity of O(n²).
It’s also worth mentioning that, depending on the use case, it may be useful to consider the space complexity of each solution. The brute force solution has a space complexity of O(n³) because it needs to store all the possible triplets. The hash table solution has a space complexity of O(n) because it uses an object to store the elements of the array.
In any case, It’s always good to have different approaches to solving a problem and to be familiar with their time and space complexities, so that you can choose the most appropriate one for your specific use case.
