# 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

```cpp
// 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.

```cpp
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.

```cpp
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;
}
```