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
}