MiddleCodeOccasionalNot answered yet
Minimum absolute difference between elements of two arrays
Given two integer arrays a and b, find the minimum of abs(a[i] - b[j]) over all pairs. You may sort the arrays in place.
Requirements:
- No extra memory beyond sorting; aim for O(n log n) then a linear merge.
- Guard against subtraction overflow and empty arrays.
long long minDistance(std::vector<int>& a, std::vector<int>& b) {
// your code here
}Write the implementation.
Sort both arrays, then walk them with two pointers. At each step record abs(a[i] - b[j]) and advance the pointer at the smaller value — moving the larger one could only widen the gap. The minimum over this merge is the global minimum. Subtract in 64-bit to avoid overflow. O(n log n).
- ✗Advancing the wrong pointer, so closer pairs are skipped
- ✗Subtracting in 32-bit ints and overflowing on extreme values
- ✗Not handling an empty array, which has no valid pair
- →Why does advancing the smaller value never miss the optimum?
- →How would
lower_boundgive an alternative O(n log n) without merging?
Contents
Task
Find the minimum abs(a[i] - b[j]) over all pairs in O(n log n).
Solution
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>
long long minDistance(std::vector<int>& a, std::vector<int>& b) {
if (a.empty() || b.empty()) return LLONG_MAX; // no valid pair
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
size_t i = 0, j = 0;
long long best = LLONG_MAX;
while (i < a.size() && j < b.size()) {
long long d = std::llabs((long long)a[i] - (long long)b[j]); // 64-bit
best = std::min(best, d);
if (a[i] < b[j]) ++i; else ++j; // advance the smaller
}
return best;
}Key points
- Sorting both plus a two-pointer merge finds the closest pair.
- Advance the smaller value's pointer — the larger one only widens the gap.
- A 64-bit subtraction guards against overflow at
INT_MIN/INT_MAX.
Contents
