# Smallest Difference

16.6 Smallest Difference: Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference. Return the difference.

``````EXAMPLE
Input: {1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}
Output: 3. That is, the pair (11 , 8).``````
• Brute force: Find min of all differences between pairs. O(N^2 + N*M), with O(N*M) extra space

• The pair itself can be found by knowing the index of the location within the array. Suppose array size 1 = 3, array size 2 = 7. Then if in the min array = index location 13 would be @ row 13 % 3 = 1 in array 1, and @ row 13 % 7 = 6. (This is basically how the index of two dimensional arrays get accessed.)

• Just realized we don't have to return the pair.

• The other approach would be to first sort both arrays, and then use two different pointers between both arrays in order to keep track of the minimum.

// Brute force

``````// to know size before compile time
template<size_t iter, size_t iter2>
int smallest_difference(array<int, iter> ar1, array<int, iter2> ar2) {
vector<int> diff;

for (auto i : ar1) {
for (auto j : ar2) {
if (i - j > 0) {
diff.push_back(i - j);
}
}
}

return *min_element(diff.begin(), diff.end());
}

int main()
{
array<int, 5> ar1 = {1,3,15,11,2};
array<int, 5> ar2 = { 23, 127, 235, 19, 8 };
cout << smallest_difference(ar1, ar2) << endl;
}``````

Implementation 2

• Not faster, just more correct. The question asks for the smallest non-negative difference. Meaning if it is negative, then we just simply just frame it the other way around, so abs should work.

``````int smallest_difference2(vector<int> &one, vector<int> & two) {
vector<int> differences;
// O(n^2)
for (auto &i : one) {
for (auto &j : two) {
differences.push_back(abs(i - j));
}
}

//O(n)
return *min_element(differences.begin(), differences.end());
}``````

Implementation 3

• Actually faster. If we sort both arrays, which takes O(nlogn) - already puts us at an advantage, because we'll now have a clear direction to navigate ourselves. The key in this problem was know that if the current element in array 1 was larger than the element in the second array, then that means if we increment array 1, the next element would be larger, and so its difference with array 2 would also be larger. So if we increment the element in array 2, that element would be larger than its previous and its difference would smaller than the previous.

``````int smallest_difference3(vector<int> &one, vector<int> & two) {
if (one.size() < 1 || two.size() < 1) return INT_MAX;

sort(one.begin(), one.end());
sort(two.begin(), two.end());

int min = INT_MAX;
int a, b;
a = b = 0;
while (a < one.size() && b < two.size()) {
int difference = abs(one.at(a) - two.at(b));
if (difference < min) {
min = difference;
}

// if one contains the lesser element,
// then incrementing would descrease the sum
if (one.at(a) < two.at(b)) {
a++;
}
else b++;
}

return min;
}``````

Last updated