# Three Number Sum

Learn the art of finding three numbers that sum to a target value with this algorithm guide. array
medium

Published At

3/5/2023

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. The function should find all triplets in the array that sum up to the target sum and return a two-dimensional array of all these triplets. The numbers in each triplet should be ordered in ascending order, and the triplets themselves should be ordered in ascending order with respect to the numbers they hold.

If no three numbers sum up to the target sum, the function should return an empty array.

### Sample Input

```js```array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0``````
```js```array = [12, 3, 1, 2, -6, 5, -8, 6]
targetSum = 0``````

### Sample Output

`js`[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]``
`js`[[-8, 2, 6], [-8, 3, 5], [-6, 1, 5]]``

### Hints

Hint 1

Using three for loops to calculate the sums of all possible triplets in the array would generate an algorithm that runs in O(n^3) time, where n is the length of the input array. Can you come up with something faster using only two for loops?̄̄̄

Hint 2

Try sorting the array and traversing it once. At each number, place a left pointer on the number immediately to the right of your current number and a right pointer on the final number in the array. Check if the current number, the left number, and the right number sum up to the target sum. How can you proceed from there, remembering the fact that you sorted the array?

Hint 3

Since the array is now sorted (see Hint #2), you know that moving the left pointer mentioned in Hint #2 one place to the right will lead to a greater left number and thus a greater sum. Similarly, you know that moving the right pointer one place to the left will lead to a smaller right number and thus a smaller sum. This means that, depending on the size of each triplet's (current number, left number, right number) sum relative to the target sum, you should either move the left pointer, the right pointer, or both to obtain a potentially valid triplet.

Optimal Space & Time Complexity

O(n^2) time | O(n) space - where n is the length of the input array

Solution-1
```js```function threeNumberSum(array, targetSum) {

/*
* Brute Force approach
* Sort the given array
* Write three nested loops
* Do the sum in every nested loop
* if equal to target sum, add it to the returning list
* return at last
*/

array.sort((a,b) => a - b)

let returningList = []

for (let i = 0; i < array.length; i++)  {
for (let j = i+1; j < array.length; j++) {
for (let k = j+1; k < array.length; k++) {
if (array[i] + array[j] + array[k] === targetSum) {
returningList.push([array[i], array[j], array[k]])
}
}
}
}

return returningList;
}``````
Solution-1
```js```function threeNumberSum(array, targetSum) {

/*
* Brute Force approach
* Sort the given array
* Write three nested loops
* Do the sum in every nested loop
* if equal to target sum, add it to the returning list
* return at last
*/

array.sort((a,b) => a - b)

let returningList = []

for (let i = 0; i < array.length; i++)  {
for (let j = i+1; j < array.length; j++) {
for (let k = j+1; k < array.length; k++) {
if (array[i] + array[j] + array[k] === targetSum) {
returningList.push([array[i], array[j], array[k]])
}
}
}
}

return returningList;
}``````
Solution-2
```js```function threeNumberSum(array, targetSum) {
array.sort((a, b) => a - b)

let returningArray = []
for (let i = 0; i < array.length; i++) {
left = i + 1;
right = array.length - 1;
while (left < right) {
let sum = array[i] + array[left] + array[right];
if (sum === targetSum) {
returningArray.push([array[i], array[left], array[right]]);
left++;
right--;
} else if (sum < targetSum) {
left++;
} else if (sum > targetSum) {
right--;
}
}
}
return returningArray;
}``````
Solution-2
```js```function threeNumberSum(array, targetSum) {
array.sort((a, b) => a - b)

let returningArray = []
for (let i = 0; i < array.length; i++) {
left = i + 1;
right = array.length - 1;
while (left < right) {
let sum = array[i] + array[left] + array[right];
if (sum === targetSum) {
returningArray.push([array[i], array[left], array[right]]);
left++;
right--;
} else if (sum < targetSum) {
left++;
} else if (sum > targetSum) {
right--;
}
}
}
return returningArray;
}``````

🎮

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.