# Smallest Difference

Tackle the problem of finding the smallest difference between elements of two different arrays with a clear algorithmic approach. array
medium

Published At

3/5/2023

Write a function that takes in two non-empty arrays of integers, finds the pair of numbers (one from each array) whose absolute difference is closest to zero, and returns an array containing these two numbers, with the number from the first array in the first position.

Note that the absolute difference of two integers is the distance between them on the real number line. For example, the absolute difference of -5 and 5 is 10, and the absolute difference of -5 and -4 is 1.

You can assume that there will only be one pair of numbers with the smallest difference.

### Sample Input

```js```arrayOne = [-1, 5, 10, 20, 28, 3]
arrayTwo = [26, 134, 135, 15, 17]``````
```js```arrayOne = [-1, 5, 10, 20, 28, 3]
arrayTwo = [26, 134, 135, 15, 17]``````

### Sample Output

`js`[28, 26]``
`js`[28, 26]``

### Hints

Hint 1

Instead of generating all possible pairs of numbers, try somehow only looking at pairs that you know could actually have the smallest difference. How can you accomplish this?

Hint 2

Would it help if the two arrays were sorted? If the arrays were sorted and you were looking at a given pair of numbers, could you efficiently find the next pair of numbers to look at? What are the runtime implications of sorting the arrays?

Hint 3

Start by sorting both arrays, as per Hint #2. Put a pointer at the beginning of both arrays and evaluate the absolute difference of the pointer-numbers. If the difference is equal to zero, then you've found the closest pair; otherwise, increment the pointer of the smaller of the two numbers to find a potentially better pair. Continue until you get a pair with a difference of zero or until one of the pointers gets out of range of its array.

Optimal Space & Time Complexity

O(nlog(n) + mlog(m)) time | O(1) space - where n is the length of the first input array and m is the length of the second input array

Solution-1
```js```function smallestDifference(arrayOne, arrayTwo) {

let returningArray = {}
for (let one of arrayOne) {
for (let two of arrayTwo) {
returningArray[Math.abs(one - two)] = [one, two]
}
}
return returningArray[Math.min(...Object.keys(returningArray))]
}``````
Solution-1
```js```function smallestDifference(arrayOne, arrayTwo) {

let returningArray = {}
for (let one of arrayOne) {
for (let two of arrayTwo) {
returningArray[Math.abs(one - two)] = [one, two]
}
}
return returningArray[Math.min(...Object.keys(returningArray))]
}``````
Solution-2
```js```// O(nLog(n) + mLog(m)) time | O(1) space
function smallestDifference(arrayOne, arrayTwo) {
let pointerOne = 0, pointerTwo = 0, difference = Infinity;

arrayOne.sort((a, b) => a - b)
arrayTwo.sort((a, b) => a - b)
let minDiff = Infinity
let minSet = []

while (pointerOne < arrayOne.length && pointerTwo < arrayTwo.length) {
let one = arrayOne[pointerOne]
let two = arrayTwo[pointerTwo]

if (one < two) {
difference = two - one
pointerOne++
} else if (two < one) {
difference = one - two
pointerTwo++
} else {
return [one, two]
}

if (difference < minDiff) {
minDiff = difference
minSet = [one, two]
}
}

return minSet

}``````
Solution-2
```js```// O(nLog(n) + mLog(m)) time | O(1) space
function smallestDifference(arrayOne, arrayTwo) {
let pointerOne = 0, pointerTwo = 0, difference = Infinity;

arrayOne.sort((a, b) => a - b)
arrayTwo.sort((a, b) => a - b)
let minDiff = Infinity
let minSet = []

while (pointerOne < arrayOne.length && pointerTwo < arrayTwo.length) {
let one = arrayOne[pointerOne]
let two = arrayTwo[pointerTwo]

if (one < two) {
difference = two - one
pointerOne++
} else if (two < one) {
difference = one - two
pointerTwo++
} else {
return [one, two]
}

if (difference < minDiff) {
minDiff = difference
minSet = [one, two]
}
}

return minSet

}``````

⚾️

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.