Problem Description

You are given a list of m arrays, where each array is sorted in ascending order. The arrays are represented as a list of lists, arrays. Your task is to find the maximum distance between any two integers, where each integer comes from a different array.

The distance between two integers a and b is |a - b|. You must select one integer from one array and another integer from a different array (i.e., you cannot pick both integers from the same array).

Constraints:

• Each array is sorted in ascending order.
• There is at least two arrays (i.e., m ≥ 2).
• Each array contains at least one element.
• All integers are within the 32-bit signed integer range.

Thought Process

The most direct way to solve this problem is to compare every possible pair of integers, ensuring each comes from a different array. However, this brute-force approach is inefficient, especially if there are many arrays or the arrays are large.

Since each array is sorted, the smallest and largest values in each array are at the beginning and end, respectively. To maximize the distance, we want to find two numbers that are as far apart as possible, ideally the smallest number from one array and the largest from another.

Rather than check every pair, we can focus on the global minimum and maximum values, but we need to ensure they come from different arrays. If the global minimum and maximum are from the same array, we need to consider the next smallest or largest from other arrays. This optimization is both intuitive and efficient.

Solution Approach

Let's break down the optimized algorithm step by step:

1. Initialization: Start by storing the minimum and maximum values from the first array. These will serve as reference points as we process the rest of the arrays.
2. Iterate through the arrays: For each subsequent array, do the following:
   • Compute the distance between the current array's minimum and the running maximum so far.
   • Compute the distance between the current array's maximum and the running minimum so far.
   • Update the answer if either distance is greater than the current maximum distance.
3. Update running minimum and maximum: After checking distances, update the running minimum and maximum if the current array's values extend the range.
4. Return the result: After processing all arrays, return the largest distance found.

This approach works because the largest possible distance will always be between the smallest and largest numbers from different arrays. By tracking the running minimum and maximum, we efficiently compare only relevant candidates.

Example Walkthrough

Let's consider the following input:

arrays = [[1, 2, 3], [4, 5], [1, 2, 3]]

1. First array: min = 1, max = 3
   Initialize min_val = 1, max_val = 3, max_distance = 0
2. Second array: min = 4, max = 5
   
   • Distance between 4 (min) and 3 (previous max): |4 - 3| = 1
   • Distance between 5 (max) and 1 (previous min): |5 - 1| = 4
   • Update max_distance = 4
   • Update min_val = 1 (still smallest), max_val = 5 (new largest)
3. Third array: min = 1, max = 3
   
   • Distance between 1 (min) and 5 (current max): |1 - 5| = 4
   • Distance between 3 (max) and 1 (current min): |3 - 1| = 2
   • max_distance remains 4
   • min_val and max_val unchanged

The answer is 4, which is the maximum distance between an element from one array and an element from a different array.

Time and Space Complexity

• Brute-Force Approach:
  • For each pair of arrays, compare every possible pair of elements.
  • If there are m arrays each of length up to n, the time complexity is O(m^2 * n^2).
  • This is inefficient and not suitable for large inputs.
• Optimized Approach:
  • We only need to iterate through each array once.
  • For each array, we do constant work: compare its min and max with running min and max.
  • The time complexity is O(m), where m is the number of arrays.
  • Space complexity is O(1), since we only store a few variables.

Summary

The key insight is that to maximize the distance between elements from different arrays, we only need to compare the minimum and maximum values across arrays, ensuring they come from different arrays. By maintaining a running minimum and maximum, we can efficiently compute the answer in a single pass, making the solution both elegant and optimal.

Code Implementation

class Solution:
    def maxDistance(self, arrays):
        min_val = arrays[0][0]
        max_val = arrays[0][-1]
        max_distance = 0
        
        for i in range(1, len(arrays)):
            curr_min = arrays[i][0]
            curr_max = arrays[i][-1]
            max_distance = max(
                max_distance,
                abs(curr_max - min_val),
                abs(max_val - curr_min)
            )
            min_val = min(min_val, curr_min)
            max_val = max(max_val, curr_max)
        return max_distance
      

class Solution {
public:
    int maxDistance(vector<vector<int>>& arrays) {
        int minVal = arrays[0][0];
        int maxVal = arrays[0].back();
        int maxDist = 0;
        for (int i = 1; i < arrays.size(); ++i) {
            int currMin = arrays[i][0];
            int currMax = arrays[i].back();
            maxDist = max(maxDist, abs(currMax - minVal));
            maxDist = max(maxDist, abs(maxVal - currMin));
            minVal = min(minVal, currMin);
            maxVal = max(maxVal, currMax);
        }
        return maxDist;
    }
};
      

class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int minVal = arrays.get(0).get(0);
        int maxVal = arrays.get(0).get(arrays.get(0).size() - 1);
        int maxDist = 0;
        for (int i = 1; i < arrays.size(); i++) {
            int currMin = arrays.get(i).get(0);
            int currMax = arrays.get(i).get(arrays.get(i).size() - 1);
            maxDist = Math.max(maxDist, Math.abs(currMax - minVal));
            maxDist = Math.max(maxDist, Math.abs(maxVal - currMin));
            minVal = Math.min(minVal, currMin);
            maxVal = Math.max(maxVal, currMax);
        }
        return maxDist;
    }
}
      

var maxDistance = function(arrays) {
    let minVal = arrays[0][0];
    let maxVal = arrays[0][arrays[0].length - 1];
    let maxDist = 0;
    for (let i = 1; i < arrays.length; i++) {
        let currMin = arrays[i][0];
        let currMax = arrays[i][arrays[i].length - 1];
        maxDist = Math.max(
            maxDist,
            Math.abs(currMax - minVal),
            Math.abs(maxVal - currMin)
        );
        minVal = Math.min(minVal, currMin);
        maxVal = Math.max(maxVal, currMax);
    }
    return maxDist;
};