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.In #624 Maximum Distance in Arrays, each array is already sorted in ascending order, and the goal is to pick one element from two different arrays such that their absolute difference is maximized. A key observation is that the largest distance will likely involve the minimum value from one array and the maximum value from another.
An efficient greedy strategy iterates through the arrays while maintaining the global min and max values seen so far from previous arrays. For each new array, compute candidate distances using its first and last elements against the tracked global extremes. This ensures that elements always come from different arrays. After evaluating, update the running minimum and maximum accordingly.
This approach avoids comparing all pairs of arrays and works in linear time relative to the number of arrays while using constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy tracking of global min and max | O(n) | O(1) |
Ashish Pratap Singh
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.
Time Complexity: O(m) where m is the number of arrays. Space Complexity: O(1) as we are only using constant extra space.
1#include <stdio.h>
2#include <math.h>
3
4int maxDistance(int** arrays, int arraysSize, int*
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.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews at large tech companies. It tests understanding of greedy reasoning, array traversal, and optimizing comparisons across multiple datasets.
No special data structure is required. Simple variables to store the running minimum and maximum values are enough, making the solution both space-efficient and easy to implement.
The optimal approach uses a greedy strategy. Track the global minimum and maximum values from previously processed arrays and compare them with the current array's extremes to compute the maximum distance.
Because each array is already sorted, the smallest and largest elements represent the extreme candidates for maximizing distance. Comparing these with previously seen global extremes guarantees the largest possible difference across different arrays.
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.