Maximum Distance in Arrays
Problem
Given m sorted arrays, return the max |a − b| where a and b come from different arrays.
arrays=[[1,2,3],[4,5],[1,2,3]]4def max_distance(arrays):
lo, hi = arrays[0][0], arrays[0][-1]; best = 0
for a in arrays[1:]:
best = max(best, a[-1] - lo, hi - a[0])
lo = min(lo, a[0]); hi = max(hi, a[-1])
return bestfunction maxDistance(arrays) {
let lo = arrays[0][0], hi = arrays[0][arrays[0].length - 1], best = 0;
for (let i = 1; i < arrays.length; i++) {
const a = arrays[i];
best = Math.max(best, a[a.length - 1] - lo, hi - a[0]);
lo = Math.min(lo, a[0]); hi = Math.max(hi, a[a.length - 1]);
}
return best;
}int maxDistance(List> arrays) {
int lo = arrays.get(0).get(0), hi = arrays.get(0).get(arrays.get(0).size() - 1), best = 0;
for (int i = 1; i < arrays.size(); i++) {
List a = arrays.get(i);
best = Math.max(best, Math.max(a.get(a.size()-1) - lo, hi - a.get(0)));
lo = Math.min(lo, a.get(0)); hi = Math.max(hi, a.get(a.size()-1));
}
return best;
} int maxDistance(vector>& arrays) {
int lo = arrays[0].front(), hi = arrays[0].back(), best = 0;
for (int i = 1; i < (int)arrays.size(); i++) {
auto& a = arrays[i];
best = max({best, a.back() - lo, hi - a.front()});
lo = min(lo, a.front()); hi = max(hi, a.back());
}
return best;
} Explanation
The biggest possible distance |a - b| always uses a very small number from one array and a very large number from a different array. Since each array is sorted, the smallest value is its first element and the largest is its last element.
The catch is that a and b must come from different arrays. So we can't just take the global minimum and global maximum if they happen to live in the same array.
The trick is a single pass that compares each new array only against everything seen before it. We keep lo = the smallest first-element so far and hi = the largest last-element so far. For a new array a, the two candidate distances are a[-1] - lo (its big end minus an earlier small start) and hi - a[0] (an earlier big end minus its small start). Both pair the new array with an earlier one, so they are automatically from different arrays.
After checking, we fold the new array into lo and hi and move on, keeping the running best.
Example: [[1,2,3],[4,5],[1,2,3]]. Start with lo=1, hi=3. At [4,5]: 5 - 1 = 4 and 3 - 4 = -1, so best = 4. The last array adds nothing better, so the answer is 4.