Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.
Example 1:
Input: [[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.
Note:
m arrays will be in the range of [2, 10000].m arrays will be in the range of [-10000, 10000].The simplest solution is to pick up every element of every array from the and find its distance from every element in all the other arrays except itself and find the largest distance from out of those.
Complexity Analysis
Time complexity : . We traverse over all the arrays in for every element of every array considered. Here, refers to the number of arrays in the and refers to the average number of elements in each array in the .
Space complexity : . Constant extra space is used.
Algorithm
In the last approach, we didn't make use of the fact that every array in the is sorted. Thus, instead of considering the distances among all the elements of all the arrays(except intra-array elements), we can consider only the distances between the first(minimum element) element of an array and the last(maximum element) element of the other arrays and find out the maximum distance from among all such distances.
Complexity Analysis
Time complexity : . We consider only max and min values directly for every array currenty considered. Here, refers to the number of arrays in the .
Space complexity : . Constant extra space is used.
Algorithm
As discussed already, in order to find out the maximum distance between any two arrays, we need not compare every element of the arrays, since the arrays are already sorted. Thus, we can consider only the extreme points in the arrays to do the distance calculations.
Further, the two points being considered for the distance calculation should not both belong to the same array. Thus, for arrays and currently chosen, we can just find the maximum out of and to find the larger distance. Here, and refer to the lengths of arrays and respectively.
But, we need not compare all the array pairs possible to find the maximum distance. Instead, we can keep on traversing over the arrays in the and keep a track of the maximum distance found so far.
To do so, we keep a track of the element with minimum value() and the one with maximum value() found so far. Thus, now these extreme values can be treated as if they represent the extreme points of a cumulative array of all the arrays that have been considered till now.
For every new array, considered, we find the distance and to compete with the maximum distance found so far. Here, refers to the number of elements in the current array, . Further, we need to note that the maximum distance found till now needs not always be contributed by the end points of the distance being and .
But, such points could help in maximizing the distance in the future. Thus, we need to keep track of these maximum and minimum values along with the maximum distance found so far for future calculations. But, in general, the final maximum distance found will always be determined by one of these extreme values, and , or in some cases, by both of them.
The following animation illustrates the process.
!?!../Documents/624_Maximum_Distance.json:1000,563!?!
From the above illustration, we can clearly see that although the or could not contribute to the local maximum distance values, they could later on contribute to the maximum distance.
Complexity Analysis
Time complexity : . We traverse over the of length once only.
Space complexity : . Constant extra space is used.
Analysis written by: @vinod23