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