Maximum Distance in Arrays

Problem Statement

Given several arrays where each individual array is sorted in ascending order, the task is to determine the largest possible absolute difference between any two elements, each taken from a different array. The absolute difference between two integers a and b is defined as |a - b|. The goal is to compute this maximum distance to understand how spread apart the elements from two distinct arrays can be.

Examples

Example 1

Input:

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

Output:

4

Explanation:

One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Example 2

Input:

arrays = [[1],[1]]

Output:

0

Constraints

• m == arrays.length
• 2 <= m <= 105
• 1 <= arrays[i].length <= 500
• -104 <= arrays[i][j] <= 104
• arrays[i] is sorted in ascending order.
• There will be at most 105 integers in all the arrays.

Approach and Intuition

When attempting to solve the problem of finding the maximum distance by selecting one number from two different arrays, consider the following approach:

1. Recognize that the maximum distance can only be achieved by considering the smallest or largest values in each array because the arrays are sorted. The minimum or maximum values will inherently provide the greatest difference.

2. To maximize the absolute difference |a - b|, one would typically look to subtract the smallest number in one array from the largest number in another array.

   • Given the data within two arrays [1, 3, 5] and [2, 6, 8], the potentially largest difference would be between the smallest number of the first array (1) and the largest number of the second array (8) or vice versa.

3. Practical step-by-step plan:

   • Initialize two variables, globalMin and globalMax, to track the maximum of min values from all arrays and the minimum of max values across all arrays, respectively.
   • Loop through each array:
     1. For each array, identify its local minimum and maximum.
     2. Update globalMax and globalMin by comparing current array's values with global values.
   • Finally, the desired maximum distance will be the difference between globalMax and globalMin.

Considering the constraints:

• Due to the problem's requirements, the approach above is efficient because it processes each array individually and makes use of the property that each individual array is already sorted.
• The operations per array are constant and only involve retrieving the first and last elements due to the arrays' sorted nature.
• This results in a time complexity proportional to the number of arrays, making it scalable up to the upper limit of the provided constraints.

Solutions

class Solution {
    public int findMaxDiff(List<List<Integer>> listArrays) {
        int maximumDiff = 0;
        int firstSize = listArrays.get(0).size();
        int smallestValue = listArrays.get(0).get(0);
        int largestValue = listArrays.get(0).get(firstSize - 1);
        for (int index = 1; index < listArrays.size(); index++) {
            firstSize = listArrays.get(index).size();
            maximumDiff = Math.max(maximumDiff, Math.max(Math.abs(listArrays.get(index).get(firstSize - 1) - smallestValue), 
                                                         Math.abs(largestValue - listArrays.get(index).get(0))));
            smallestValue = Math.min(smallestValue, listArrays.get(index).get(0));
            largestValue = Math.max(largestValue, listArrays.get(index).get(firstSize - 1));
        }
        return maximumDiff;
    }
}