Maximum Distance in Arrays

Med

#0580Time: 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.

Patterns

Greedy

Data structures

Array

Prompt

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.length
2 <= m <= 10⁵
1 <= arrays[i].length <= 500
-10⁴ <= arrays[i][j] <= 10⁴
arrays[i] is sorted in ascending order.
There will be at most 10⁵ integers 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_distance to 0.
Use a nested loop to iterate through each unique pair of arrays (arrays[i], arrays[j]) where i < 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_distance with the maximum of max_distance, dist1, and dist2.
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.

1import java.util.List;2 3class Solution {4    public int maxDistance(List<List<Integer>> arrays) {5        int maxDist = 0;6        for (int i = 0; i < arrays.size(); i++) {7            for (int j = i + 1; j < arrays.size(); j++) {8                List<Integer> list1 = arrays.get(i);9                List<Integer> list2 = arrays.get(j);10                11                int min1 = list1.get(0);12                int max1 = list1.get(list1.size() - 1);13                14                int min2 = list2.get(0);15                int max2 = list2.get(list2.size() - 1);16                17                maxDist = Math.max(maxDist, Math.abs(max2 - min1));18                maxDist = Math.max(maxDist, Math.abs(max1 - min2));19            }20        }21        return maxDist;22    }23}

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.

A more efficient approach is to iterate through the arrays just once, keeping track of the minimum and maximum values encountered so far. In each step, we calculate the maximum possible distance between the current array and all previously seen arrays.

Algorithm

Initialize max_distance to 0.
Initialize min_val to the first element of the first array (arrays[0][0]).
Initialize max_val to the last element of the first array (arrays[0][last]).
Iterate through the arrays from the second array (i = 1) to the end.
In each iteration, get the current array's minimum (current_min) and maximum (current_max).
Calculate the potential new maximum distance by taking the maximum of:
- The current max_distance.
- The absolute difference between current_max and the global min_val seen so far.
- The absolute difference between the global max_val seen so far and current_min.
Update max_distance with this new maximum.
Update the global min_val by taking min(min_val, current_min).
Update the global max_val by taking max(max_val, current_max).
After the loop, return max_distance.

Walkthrough

We can optimize the process by making a single pass through the list of arrays. We maintain two variables: min_val, the smallest element seen across all arrays visited so far, and max_val, the largest element seen. We initialize these with the min and max of the first array. Then, we iterate from the second array onwards. For each new array, we calculate the potential maximum distance by comparing its smallest element with the max_val seen so far, and its largest element with the min_val seen so far. This is because we are trying to find a pair from two different arrays. The min_val and max_val represent the extremes from the set of previously visited arrays. After checking for a new maximum distance, we update min_val and max_val with the current array's endpoints to include them in the consideration for subsequent arrays.

1import java.util.List;2 3class Solution {4    public int maxDistance(List<List<Integer>> arrays) {5        int maxDist = 0;6        7        // Initialize min and max with the first array's values8        List<Integer> firstList = arrays.get(0);9        int minVal = firstList.get(0);10        int maxVal = firstList.get(firstList.size() - 1);11        12        // Iterate from the second array13        for (int i = 1; i < arrays.size(); i++) {14            List<Integer> currentList = arrays.get(i);15            int currentMin = currentList.get(0);16            int currentMax = currentList.get(currentList.size() - 1);17            18            // Calculate max distance with the current array and the values from previous arrays19            maxDist = Math.max(maxDist, Math.abs(currentMax - minVal));20            maxDist = Math.max(maxDist, Math.abs(maxVal - currentMin));21            22            // Update the overall min and max values seen so far23            minVal = Math.min(minVal, currentMin);24            maxVal = Math.max(maxVal, currentMax);25        }26        27        return maxDist;28    }29}

Complexity

Time

O(m), where m is the number of arrays. We iterate through the list of arrays only once.

Space

O(1), as we only use a few variables to store the running minimum, maximum, and the result.

Trade-offs

Pros

Highly efficient with linear time complexity.
Optimal in terms of both time and space.

Cons

The logic is slightly more abstract than the brute-force method.

Solutions

Solution

1class 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 ; } }

1/** * @param {number[][]} arrays * @return {number} */ var maxDistance =2  function (arrays) {3    const n = arrays.length;4    let res = 0;5    let [min, max] = [Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY];6    for (let i = 0; i < n; i++) {7      const a = arrays[i];8      res = Math.max(Math.max(a.at(-1) - min, max - a[0]), res);9      min = Math.min(min, a[0]);10      max = Math.max(max, a.at(-1));11    }12    return res;13  };

1class Solution { public: int maxDistance ( vector < vector < int >>& arrays ) { int ans = 0 ; int mi = arrays [ 0 ][ 0 ], mx = arrays [ 0 ][ arrays [ 0 ]. size () - 1 ]; for ( int i = 1 ; i < arrays . size (); ++ i ) { auto & arr = arrays [ i ]; int a = abs ( arr [ 0 ] - mx ), b = abs ( arr [ arr . size () - 1 ] - mi ); ans = max ({ ans , a , b }); mi = min ( mi , arr [ 0 ]); mx = max ( mx , arr [ arr . size () - 1 ]); } return ans ; } };

1class Solution : def maxDistance ( self , arrays : List [ List [ int ]]) -> int : ans = 0 mi , mx = arrays [ 0 ][ 0 ], arrays [ 0 ][ - 1 ] for arr in arrays [ 1 :]: a , b = abs ( arr [ 0 ] - mx ), abs ( arr [ - 1 ] - mi ) ans = max ( ans , a , b ) mi = min ( mi , arr [ 0 ]) mx = max ( mx , arr [ - 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.

← Previous

Previous problem

Next problem