CoDEVIANT #17 (10/3/20) — Pick T̶h̶r̶e̶e̶ Two, M’Lord
Problem:
Let’s write a function that takes two non-empty arrays of integers. This function will find the pair of numbers (one from each array) whose absolute difference is the closest to zero.
Then the function returns the values from each array in a new array like so:
[valueFromArray1, valueFromArray2]In other words:
So I’m super jazzed to say that thanks to the thing I learned about pointers in the last coDEVIANT article, I was able to apply similar logic and find a solution.
Et voila:
function smallestDifference(arrayOne, arrayTwo) {
let unoCounter = 0
let dosCounter = 0
let computedValue = null
for(let i = 0; i < arrayOne.length; i ++) {
arrayTwo.forEach((el, index) => {
let value = Math.abs(el - arrayOne[i])
if(computedValue === null || value < computedValue) {
computedValue = value
unoCounter = i
dosCounter = index
}
})
}
return [ arrayOne[unoCounter], arrayTwo[dosCounter] ]
}So let’s get the easy stuff down first.
Anyways…
We create two variables that equal 0 to start: unoCounter and dosCounter. Then we create a variable called computedValue which equals null.
let unoCounter = 0
let dosCounter = 0
let computedValue = nullNext we are going to create a classic for-loop that iterates through the arrayOne argument that is passed into the function. It will have i start at 0, keep going through the length of arrayOne and will augment i by one each round.
for(let i = 0; i < arrayOne.length; i++) {
.....
}Next we’re going to use the forEach array-method inside of this for-loop on the arrayTwo argument passed into the function.
for(let i = 0; i < arrayOne.length; i++) {
arrayTwo.forEach(el => {
...
})
}Inside the forEach method, we:
- Create a new variable called value which will equal the absolute value of el minus whatever value is represented by arrayOne[i] at that moment.
for(let i = 0; i < arrayOne.length; i++) {
arrayTwo.forEach(el => {
let value = Math.abs(el - arrayOne[i])
})
}Right under where we established the value variable, we create an if-statement saying that if computedValue equals null or if value is less than computedValue, we:
- set computedValue to equal whatever value is
- set unoCounter to equal whatever i from the classic for-loop is
- set dosCounter to equal index from the use of the forEach-array method ((When you use forEach the first argument, el, in our case, is the value of the array-element. The second argument, index, in our case, is the array-index where the value is located))
for(let i = 0; i < arrayOne.length; i++) {
arrayTwo.forEach(el => {
let value = Math.abs(el - arrayOne[i])
if(computedValue === null || value < computedValue) {
computedValue = value
unoCounter = i
dosCounter = index
}
})
}Then we return an array with the first element being whatever value is at arrayOne[unoCounter] and the second element being whatever value is at arrayTwo[dosCounter].
return [ arrayOne[unoCounter], arrayTwo[dosCounter] ]Full solution again:
function smallestDifference(arrayOne, arrayTwo) {
let unoCounter = 0
let dosCounter = 0
let computedValue = null
for(let i = 0; i < arrayOne.length; i ++) {
arrayTwo.forEach((el, index) => {
let value = Math.abs(el - arrayOne[i])
if(computedValue === null || value < computedValue) {
computedValue = value
unoCounter = i
dosCounter = index
}
})
}
return [ arrayOne[unoCounter], arrayTwo[dosCounter] ]
}I plugged my solution in, ran it, and all the test-cases passed.
How did the super-nerds do it?…
function smallestDifference(arrayOne, arrayTwo) {
arrayOne.sort((a,b) => a-b)
arrayTwo.sort((a,b) => a-b) let idxOne = 0
let idxTwo = 0
let smallest = Infinity
let current = Infinity
let smallestPair = [] while(idxOne < arrayOne.length && idxTwo < arrayTwo.length){
let firstNum = arrayOne[idxOne]
let secondNum = arrayTwo[idxTwo]
if(firstNum < secondNum){
current = secondNum - firstNum
idxOne++
} else if(secondNum < firstNum){
current = firstNum - secondNum
idxTwo++
} else {
return [firstNum, secondNum]
} if(smallest > current) {
smallest = current
smallestPair = [firstNum, secondNum]
}
}
return smallestPair
}
So what’s interesting about this solution is that it only uses one loop, a while-loop, to drive the calculation. My solution used two for-loops (one was a classic for-loop and the other is implied by the use of the forEach array-method). This is a better, more lightweight (computationally speaking) solution because, unlike mine, this does NOT compare every single possible combination in order to find the smallest pair.
And now it is…
First we sort the arrays that are passed in as arguments. We want to have these arrays in ascending order.
arrayOne.sort((a,b)=> a - b)
arrayTwo.sort((a,b)=> a - b)Then we create some variables to help us keep track of things:
- idxOne: the counter for arrayOne; set to 0
- idxTwo: the counter for arrayTwo; set to 0
- smallest: to keep track of the smallest difference; initially set to Infinity so that no matter what the first difference between values is, it is smaller.
- current: to keep track of the current difference between the two values presently at play; initially set to Infinity as well
- smallestPair: an empty array that will hold the appropriate value from each of the arrays; this is the answer we will return in our function
let idxOne = 0
let idxTwo = 0
let smallest = Infinity
let current = Infinity
let smallestPair = []Now we create a while-loop, which will remain active as long as idxOne is smaller than the length of arrayOne AND as long as idxTwo is smaller than the length of arrayTwo. The way we will be setting up our logic in this while-loop is such that if either of the pointers exceed the length of their respective arrays, because we’ve sorted the arrays in ascending order, we will have our answer to put into smallestPair which we can then return.
while(idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
...
}Now inside the while-loop, we’re going to set up two variables:
- firstNum: the value at arrayOne at the position indicated by idxOne
- secondNum: the value at arrayTwo at the position indicated by idxTwo
while(idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
let firstNum = arrayOne[idxOne]
let secondNum = arrayTwo[idxTwo]
}Next we set up an if-else-statement with three levels. It will compare the difference between firstNum and secondNum (or vice-versa) depending on which one is larger. If firstNum is larger, then idxOne gets increased by one. If secondNum is larger, then idxTwo gets increased by one. If they are the same, then that means the difference is 0, we can pack our bags, return whatever firstNum and secondNum are immediately and call it a day.
Immediately under the if-else statement, we create another if-statement stating that if the value of our smallest variable is larger than current, we set smallest to equal whatever value current presently has. smallestPair is also set to equal an array containing firstNum as its first element and secondNum as its second element.
while(idxOne < arrayOne.length && idxTwo < arrayTwo.length) {
let firstNum = arrayOne[idxOne]
let secondNum = arrayTwo[idxTwo] if(firstNum < secondNum) {
current = secondNum - firstNum
idxOne++
} else if(secondNum < firstNum){
current = firstNum - secondNum
idxTwo++
} else {
return [firstNum, secondNum]
} if(smallest > current) {
smallest = current
smallestPair = [firstNum, secondNum]
}
}
So before we go any further, let’s break logically what’s happening here.
Let’s say we have our sorted arrays:
- arrayOne = [-1, 3, 5, 10, 20, 28]
- arrayTwo = [15, 17, 26, 134, 135]
At the start of the first run of the while-loop, firstNum is going to be -1 and secondNum is going to be 15.
In our if-else statement, we’re going to playing with the first if-block because our situation is such that firstNum is less than secondNum. In this case current equals 15 minus 1, which, according to my remedial math skills, equals 14.
We stroll on down to the subsequent if-statement and compare our current (at this point 14) to smallest (at this point Infinity). Plot twist (j/k) 14 is smaller than Infinity, so smallest becomes 14. smallestPair also becomes [-1, 15].
At this point we have reached the end of a cycle of our while-loop that our if-else statement and if statement are inside of. The while loop doesn’t stop until either idxOne or idxTwo are larger than the length of their respective arrays, however. So we repeat this again, except this time while idxTwo is still 0, idxOne is 1. The image below details how the while-loop (with its inner if-else statement and if-statement) churn out the answer for us.
When firstNum was smaller than secondNum, we increased idxOne to see if we could get a value that would yield a smaller difference, and vice-versa. This is the driving calculation behind this better answer: an answer that doesn’t need to figure out every single possible calculation and then give us a report. This sucker only needed 6 turns to get us the pair with the smallest difference.
The answer again:
function smallestDifference(arrayOne, arrayTwo) {
arrayOne.sort((a,b) => a-b)
arrayTwo.sort((a,b) => a-b)let idxOne = 0
let idxTwo = 0
let smallest = Infinity
let current = Infinity
let smallestPair = []while(idxOne < arrayOne.length && idxTwo < arrayTwo.length){
let firstNum = arrayOne[idxOne]
let secondNum = arrayTwo[idxTwo]
if(firstNum < secondNum){
current = secondNum - firstNum
idxOne++
} else if(secondNum < firstNum){
current = firstNum - secondNum
idxTwo++
} else {
return [firstNum, secondNum]
}if(smallest > current) {
smallest = current
smallestPair = [firstNum, secondNum]
}
}
return smallestPair
}
I really liked this problem because I felt really good about being able to solve it the first time by myself. The better solution was great because it introduced me the Infinite JavaScript concept and gave me another way to leverage pointers with arrays. All in all, it was a good day.
Thanks so much for checking out this edition of coDEVIANT. If you have any questions, comments, or concerns drop a comment. If this was useful or you enjoyed my attempt at making this guide humorous and accessible, give me a clap, or better yet, a follow!
Ok, nerds…