Maximum Distance in Arrays - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You are given multiple sorted arrays. Pick one element from one array and another element from a different array. The goal is to maximize the absolute difference |a - b|. Because each array is already sorted, the only candidates that matter are the first (minimum) and last (maximum) elements of each array.
Approach 1: Brute Force Comparison (O(n²) time, O(1) space)
The direct approach compares every pair of arrays. For each pair (i, j), compute two candidate distances: |arrays[i][0] - arrays[j][-1]| and |arrays[j][0] - arrays[i][-1]|. Since arrays are sorted, the extreme values produce the largest differences. Iterate through all pairs and track the maximum distance. This approach is simple and clearly shows the key observation about using only boundary elements, but the nested iteration results in O(n²) time where n is the number of arrays. It works fine for small inputs but does unnecessary comparisons.
Approach 2: Minimum and Maximum Tracking (Greedy) (O(n) time, O(1) space)
A more efficient solution keeps track of the smallest value and largest value seen so far while iterating through the arrays once. Start with the first array's minimum and maximum. For every subsequent array, compute two candidate distances: the difference between its maximum and the global minimum, and the difference between the global maximum and its minimum. Update the result with the larger of these two values. After processing the array, update the global minimum and maximum if needed. This works because the optimal pair must involve extremes across different arrays, and processing sequentially guarantees the values come from different arrays.
This technique is essentially a greedy strategy over arrays. Instead of comparing all combinations, you only maintain the best extremes encountered so far. Each array contributes at most two comparisons, which keeps the total work linear in the number of arrays.
Recommended for interviews: The greedy minimum/maximum tracking solution is the expected answer. Interviewers want to see that you recognize the sorted property and reduce the problem to comparing boundary values. Mentioning the brute force approach first shows understanding of the search space, but implementing the greedy linear pass demonstrates optimization skills and awareness of time complexity tradeoffs.
Approach 1: Using Minimum and Maximum Tracking
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.
Complexity
Time Complexity: O(m) where m is the number of arrays. Space Complexity: O(1) as we are only using constant extra space.
Approach 2: Brute Force Comparison
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.
Complexity
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 3: Maintain Maximum and Minimum Values
We notice that the maximum distance must be the distance between the maximum value in one array and the minimum value in another array. Therefore, we can maintain two variables mi and mx, representing the minimum and maximum values of the arrays we have traversed. Initially, mi and mx are the first and last elements of the first array, respectively.
Next, we traverse from the second array. For each array, we first calculate the distance between the first element of the current array and mx, and the distance between the last element of the current array and mi. Then, we update the maximum distance. At the same time, we update mi = min(mi, arr[0]) and mx = max(mx, arr[size - 1]).
After traversing all arrays, we get the maximum distance.
The time complexity is O(m), where m is the number of arrays. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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. |
| Maintain Maximum and Minimum Values | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n²) | O(1) | Useful for understanding the problem or when the number of arrays is very small |
| Minimum and Maximum Tracking (Greedy) | O(n) | O(1) | Best approach for interviews and production code; processes arrays in a single pass |
Video Solution
Maximum Distance in Arrays - Leetcode 624 - Python • NeetCodeIO • 13,727 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Distance in Arrays easy or hard?
Maximum Distance in Arrays Python/Java solution
How to solve Maximum Distance in Arrays in O(n)?
What is the best approach for Maximum Distance in Arrays?
Is Maximum Distance in Arrays asked at Google/Amazon/Meta?
What data structure is used in Maximum Distance in Arrays?
What is the time complexity of Maximum Distance in Arrays?
Ready to solve this problem?
Practice Maximum Distance in Arrays with our built-in code editor and test cases.
Practice on FleetCode