# CoDEVIANT #16 (10/2/20) — When arrays are like Tetris

--

Problem 1:

We get a non-empty array of distinct integers and an integer representing a target sum. We need to create a function that finds all the triplets in the array that will, when added together, return the target sum. We also need to return a two-dimensional array of all these triplets. If that wasn’t enough, we also have to make sure each triplet has its members ordered in ascending order (i.e. lowest to the left with us going higher as we go right). If no triplets are made that fit the bill outlined above, then we should just return an empty array.

My attempt at a solution was this:

`function threeNumberSum(array, targetSum) {`

let arr = []

for(let i = 0; i < array.length - 1; i++) {

for(let c = i + 1; c < array.length; c++) {

for(let p = c + 1; p < array.length; p++) {

if(array[i] + array[c] + array[p] == targetSum) {

arr.push([array[i], array[c], array[p]])

}

}

}

}

return arr

}

To start, I create a new variable called **arr **which will be an empty array. It is in this that we will push our triplet arrays we’re seeking.

I use three for-loops iterating over the array passed into the function. I do this with the index counters (i, c, and p) being successively one larger than the previous one. This facilitates the whole triplet-seeking action that we need.

Inside the body of the third and innermost for-loop I say that if the value of array[i] + array[c] + array[p] equals the targetSum, then we should push into **arr** an array containing:

- array[i]
- array[c]
- array[p]

at whatever values they are at that instant, because they are the ones equaling our targetValue.

Then I return **arr**.

And this mostly works for the test-cases my algorithm is put through, however, I frequently run into the issue of my triplet arrays inside of **arr** not being in ascending order.

I’ll get error messagse saying that the test failed because it was expecting something like:**[[-2, 10, 49]]** and I was returning *[[10, -2, 49]].*

Basically, I needed to Tetris that shit and I couldn’t figure out how.

Actually, it was a little more like this:

So what was the proper and thorough way to solve it, you ask? Gather round, kiddies, and I’ll tell ye a tale of some dope shit that makes me feel smarter to be able to explain it accurately.

The solution:

`function threeNumberSum(array, targetSum) {`

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

return a - b

})

let triplets = []

for(let i = 0; i < array.length - 2; i++) {

let left = i + 1

let right = array.length - 1

while(left < right ) {

let currentSum = array[i] + array[left] + array[right]

if(currentSum === targetSum) {

triplets.push([ array[i], array[left], array[right] ])

left++

right--

} else if(currentSum < targetSum) {

left++

} else if(currentSum > targetSum) {

right--

}

}

}

return triplets

}

First: We sort the array passed as an argument into the function in ascending order. We accomplish this by using the addition arguments you can pass into the array method *sort* to detail a callback that allows you to define how you want the sorting action to work.

`array.sort((a, b) => {`

return a - b

})

With the above line, what would have been this for our passed in array:

[12, 3, 1, 2, -6, 5, -8, 6]

is now: [-8, -6, 1, 2, 3, 5, 6, 12]

Then we set a variable called *triplets* to be an empty array. This is where we will pass our triplet arrays into later on.

`let triplets = []`

Here’s where the big crazy stuff starts so hold on to your hats.

We start a for loop that iterates over the array we just sorted. We say that *i* will equal 0, we keep looping as long as *i* is lower than the length of the sorted-array minus 2 ***TODO***, and for each iteration — *i* is increased by one.

`for(let i = 0; i < array.length - 2; i++ {`

...

}

Inside our for-loop, we establish variables that we’ll use as **‘pointers’**. They will be called *left (which will equal **i + 1**) *and *right (which will equal **array.length -1**)*.

for(let i = 0; i < array.length - 2; i++ {

let left = i + 1

let right = array.length - 1 ...

}

Within the for-loop, after our declaring of *left* and *right*. We are going to write a while-loop which will keep its contents running so long as *left* is less than *right. *Inside the while-loop, we create the *currentSum* variable which will equal: **array[i] + array[left] + array[right] .**

Then we say that if *currentSum* is equal to *targetSum*(the value passed into the function that we’re seeking our triplets to equal), we get the values in bold above, cast them into an array and push that array to the **triplets array**. Then, because we are still exploring what combinations are still viable to make suitable combinations with *i* in the for-loop being what it currently is, we move the *left* value to be one larger than it already is and the *right* value to be one less than it currently is. So long as *left* is lower than *right*, a new value will not be set onto *i.*

`while(left < right ) {`

let currentSum = array[i] + array[left] + array[right]

if(currentSum === targetSum) {

triplets.push([ array[i], array[left], array[right] ])

left++

right--

}

}

But what if the *currentSum* is smaller or bigger than *targetSum*?

Well, if the *currentSum* is smaller than the *targetSum*, we increase *left* by one. This causes the value of array[left] to be larger than it was just a second before because the array has been sorted in an ascending order. If the *currentSum *is larger than the *targetSum*, we decrease *right *by one. This causes the value of array[right] to be smaller.

`while(left < right ) {`

let currentSum = array[i] + array[left] + array[right]

if(currentSum === targetSum) {

triplets.push([ array[i], array[left], array[right] ])

left++

right--

} else if(currentSum < targetSum) {

left++

} else if(currentSum > targetSum) {

right--

}

}

We keep doing this until we get our full set of triplets. Since we sorted everything in ascending order from the very get go, we don’t have to worry about the Tetris issue I ran into with my many for-loops. And don’t worry about creating an unending loop. Once *left *is equal to or greater than *right* on the final iteration of the for-loop, the code returns our *triplets* array, and we’re home free.

Here’s the final code once again:

`function threeNumberSum(array, targetSum) {`

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

return a - b

})

let triplets = []

for(let i = 0; i < array.length - 2; i++) {

let left = i + 1

let right = array.length - 1

while(left < right ) {

let currentSum = array[i] + array[left] + array[right]

if(currentSum === targetSum) {

triplets.push([ array[i], array[left], array[right] ])

left++

right--

} else if(currentSum < targetSum) {

left++

} else if(currentSum > targetSum) {

right--

}

}

}

return triplets

}