Maximum Distance in Arrays
MedPrompt
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.- There will be at most
105integers in all the arrays.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to consider every possible pair of different arrays. For each pair, we calculate the maximum possible distance between them and keep track of the overall maximum distance found.
Algorithm
- Initialize a variable
max_distanceto 0. - Use a nested loop to iterate through each unique pair of arrays
(arrays[i], arrays[j])wherei < j. - For each pair, find the minimum element (first element) and maximum element (last element) of both arrays.
- Calculate the distance between the maximum of one array and the minimum of the other:
dist1 = |arrays[j].last - arrays[i].first|. - Calculate the distance between the minimum of one array and the maximum of the other:
dist2 = |arrays[i].last - arrays[j].first|. - Update
max_distancewith the maximum ofmax_distance,dist1, anddist2. - After iterating through all pairs, return
max_distance.
Walkthrough
This method systematically checks every combination of two distinct arrays. Since the arrays are sorted, the maximum distance between any two arrays, say array_i and array_j, must involve their endpoints. Specifically, the distance will be either between the minimum of array_i and the maximum of array_j, or the maximum of array_i and the minimum of array_j. We can iterate through all pairs of arrays (i, j) with i < j, calculate these two potential distances, and update a global maximum distance.
import java.util.List; class Solution { public int maxDistance(List<List<Integer>> arrays) { int maxDist = 0; for (int i = 0; i < arrays.size(); i++) { for (int j = i + 1; j < arrays.size(); j++) { List<Integer> list1 = arrays.get(i); List<Integer> list2 = arrays.get(j); int min1 = list1.get(0); int max1 = list1.get(list1.size() - 1); int min2 = list2.get(0); int max2 = list2.get(list2.size() - 1); maxDist = Math.max(maxDist, Math.abs(max2 - min1)); maxDist = Math.max(maxDist, Math.abs(max1 - min2)); } } return maxDist; }}Complexity
Time
O(m^2), where m is the number of arrays. We use nested loops to iterate through all unique pairs of arrays.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small inputs.
Cons
Inefficient for a large number of arrays, leading to a Time Limit Exceeded (TLE) error on larger test cases.
Solutions
Solution
class Solution { public int maxDistance ( List < List < Integer >> arrays ) { int ans = 0 ; int mi = arrays . get ( 0 ). get ( 0 ); int mx = arrays . get ( 0 ). get ( arrays . get ( 0 ). size () - 1 ); for ( int i = 1 ; i < arrays . size (); ++ i ) { var arr = arrays . get ( i ); int a = Math . abs ( arr . get ( 0 ) - mx ); int b = Math . abs ( arr . get ( arr . size () - 1 ) - mi ); ans = Math . max ( ans , Math . max ( a , b )); mi = Math . min ( mi , arr . get ( 0 )); mx = Math . max ( mx , arr . get ( arr . size () - 1 )); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.