# Better optimize smallest difference

Page 1 of 1

## 2 Replies - 251 Views - Last Post: 13 January 2020 - 12:58 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=418243&amp;s=7bc6db0ac69bc40fbc53a3e90d1cad83&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 fearfulsc2

• D.I.C Regular

Reputation: 18
• Posts: 301
• Joined: 25-May 16

# Better optimize smallest difference

Posted 13 January 2020 - 10:29 AM

Hi everyone, I'm having a little fun with trying to come up with algorithms that have a better time/space complexity.

I came across this one problem where I am given two different arrays (can be in any order and any positive/negative integer is allowed) and I must find the smallest difference between the two arrays.

So if the difference between the first array and second array are 0, that would be the smallest difference since that means they are equal to each other.

To make things simpler, we will assume that there is only one pair that has the smallest difference. When you find it, you then output the pair in an array with those 2 values.

The solution below is my solution and I was wondering if there was a more efficient or better way to do this.

Worst case scenario, my solution is O(n2) time complexity and O(1) space

What do you all think?

```using System;
public class Program {
public static int[] SmallestDifference(int[] arrayOne, int[] arrayTwo) {
int smallest = Int32.MaxValue;
int[] smallestDiff = new int[] { 0, 0 };

for(int i = 0; i < arrayOne.Length; i++)
{
for(int j = 0; j < arrayTwo.Length; j++)
{
if(Math.Abs(arrayOne[i] - arrayTwo[j]) < smallest)
{
smallest = Math.Abs(arrayOne[i] - arrayTwo[j]);
smallestDiff[0] = arrayOne[i];
smallestDiff[1] = arrayTwo[j];
}
}
}

return smallestDiff;
}
}

```

Is This A Good Question/Topic? 1

## Replies To: Better optimize smallest difference

### #2 Skydiver

• Code herder

Reputation: 7244
• Posts: 24,556
• Joined: 05-May 12

## Re: Better optimize smallest difference

Posted 13 January 2020 - 12:26 PM

Sort first and second arrays separately. Do a merge sort keeping track of the differences between first and second sorted array elements.

### #3 Skydiver

• Code herder

Reputation: 7244
• Posts: 24,556
• Joined: 05-May 12

## Re: Better optimize smallest difference

Posted 13 January 2020 - 12:58 PM

On thinking some more, just sort the first array. Then using values from the second array, do a pretend insertion sort or a binary search on the first sorted array. Compute differences between the neighbors of where the value would go.