You are given m arrays, where each array is sorted in ascending order.
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|.
Return the maximum distance.
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.length2 <= m <= 1051 <= arrays[i].length <= 500-104 <= arrays[i][j] <= 104arrays[i] is sorted in ascending order.105 integers in all the arrays.One simple yet effective way to tackle this problem is to track the minimum and maximum values as we iterate over the arrays, since each array is sorted in ascending order. We initialize the maximum distance as zero. For each array except the first one, calculate the possible distance using the current array's first element with the global maximum, and the current array's last element with the global minimum. Update the global minimum and maximum as you traverse each array. This approach ensures all distance calculations only consider meaningful pairs from different arrays and efficiently computes the result in a single pass.
This solution iterates over the given arrays while keeping track of the global minimum and maximum values seen so far. It utilizes these for calculating potential maximum distances between the current array's element boundaries and previous minima/maxima without redundant calculations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m) where m is the number of arrays. Space Complexity: O(1) as we are only using constant extra space.
A naive brute force approach would involve iterating over each pair of arrays and comparing all possible combinations of elements from both arrays. While this method ensures completeness of coverage for all potential maximum distance computations, it results in a less efficient O(m2 * n) complexity where n is the average number of elements in one array. It serves as a solid baseline comparison for the more efficient approach.
The brute force solution systematically checks distance calculations across every possible pair of separate arrays, albeit with lesser theoretical efficiency due to the intrinsic nested loop structure causing significant execution time overhead.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m2 * n) where m is the number of arrays and n is the average number of elements in each array. Space Complexity: O(1), constant space aside from an output variable.
| Approach | Complexity |
|---|---|
| Using Minimum and Maximum Tracking | Time Complexity: O(m) where m is the number of arrays. Space Complexity: O(1) as we are only using constant extra space. |
| Brute Force Comparison | Time Complexity: O(m2 * n) where m is the number of arrays and n is the average number of elements in each array. Space Complexity: O(1), constant space aside from an output variable. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,131 views views
Watch 9 more video solutions →Practice Maximum Distance in Arrays with our built-in code editor and test cases.
Practice on FleetCode