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.
\n\nComplexity Analysis
\nTime 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 .
\nSpace complexity : . Constant extra space is used.
\nAlgorithm
\nIn 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.
\n\nComplexity Analysis
\nTime complexity : . We consider only max and min values directly for every array currenty considered. Here, refers to the number of arrays in the .
\nSpace complexity : . Constant extra space is used.
\nAlgorithm
\nAs 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.
\nFurther, 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.
\nBut, 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.
\nTo 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.
\nFor 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 .
\nBut, 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.
\nThe following animation illustrates the process.
\n!?!../Documents/624_Maximum_Distance.json:1000,563!?!
\nFrom 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.
\n\nComplexity Analysis
\nTime complexity : . We traverse over the of length once only.
\nSpace complexity : . Constant extra space is used.
\nAnalysis written by: @vinod23
\n