Maximum Distance in Arrays

How it works

We can do better by making a single pass. As we scan through the arrays, we maintain the global minimum and maximum seen so far. For each new array, the best distance involving this array is either current_max - global_min or global_max - current_min. After checking, we update our global min and max to include the current array's values.

The key insight is that we compare the current array against all previous arrays implicitly through the running min and max. This guarantees the two elements come from different arrays.

Steps

1. Initialize min_val and max_val from the first array.
2. For each subsequent array:
   • Compute the distance using current_last - min_val and max_val - current_first.
   • Update the result with the maximum of these distances.
   • Update min_val and max_val to include the current array's first and last elements.
3. Return the result.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) constant space used

Where n is the number of arrays in arrays

Things to watch for

Selecting Both Elements from the Same Array

The problem requires elements to come from two different arrays. A common mistake is to find the global minimum and maximum across all elements without ensuring they belong to different arrays. For example, if one array contains both the smallest and largest values, using them would violate the constraint. The single scan solution handles this by comparing the current array's values against previously seen min/max values, guaranteeing they come from different arrays.

Forgetting to Use Absolute Difference

Some solutions compute the difference without taking the absolute value. While the optimal solution always involves max - min (which is positive), intermediate calculations or edge cases might produce negative values. Always use abs() or structure your comparisons to ensure you're computing |a - b| rather than just a - b.

Not Exploiting the Sorted Property of Each Array

Each individual array is sorted in ascending order. Failing to recognize this leads to unnecessarily iterating through all elements when only the first (minimum) and last (maximum) elements of each array matter. The brute force solution that checks every pair of elements is correct but inefficient; the optimized approaches leverage the sorted property to achieve linear time.

class Solution:
    def maxDistance(self, arrays: list[list[int]]) -> int:
        res = 0
        n = len(arrays[0])
        min_val = arrays[0][0]
        max_val = arrays[0][-1]
        for i in range(1, len(arrays)):
            n = len(arrays[i])
            res = max(res, max(abs(arrays[i][n - 1] - min_val),
                               abs(max_val - arrays[i][0])))
            min_val = min(min_val, arrays[i][0])
            max_val = max(max_val, arrays[i][n - 1])
        return res

class Solution {
public:
    int maxDistance(std::vector<std::vector<int>>& arrays) {
        int res = 0;
        int n = arrays[0].size();
        int min_val = arrays[0][0];
        int max_val = arrays[0][arrays[0].size() - 1];
        for (int i = 1; i < arrays.size(); i++) {
            n = arrays[i].size();
            res = std::max(res, std::max(std::abs(arrays[i][n - 1] - min_val),
                                         std::abs(max_val - arrays[i][0])));
            min_val = std::min(min_val, arrays[i][0]);
            max_val = std::max(max_val, arrays[i][n - 1]);
        }
        return res;
    }
};