#624

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Distance in Arrays

Maximum Distance in Arrays uses a greedy running minimum and maximum from previous arrays to validate cross array distance choices.

array greedy

Problem Statement

You are given m arrays where each individual array is already sorted in ascending order. From these arrays you must choose exactly one integer from one array and one integer from a different array. The distance between two chosen integers a and b is defined as the absolute difference |a - b|. Your task is to compute the largest possible distance obtainable under this rule.

For example, consider arrays = [[1,2,3],[4,5],[1,2,3]]. Choosing 1 from the first array and 5 from the second array produces a distance of 4, which is optimal. Because values must come from different arrays, you cannot simply compare elements within the same list. The challenge is efficiently identifying the largest cross array difference while respecting that constraint.

Examples

Example 1

Input: arrays = [[1,2,3],[4,5],[1,2,3]]

Output: 4

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

Example details omitted.

Constraints

m == arrays.length
2 <= m <= 105
1 <= arrays[i].length <= 500
-104 <= arrays[i][j] <= 104
arrays[i] is sorted in ascending order.
There will be at most 105 integers in all the arrays.

Solution Approach

Brute Force Using All Array Pairs

A direct approach compares every pair of arrays and computes the distance between the smallest value of one array and the largest value of the other. Because each array is sorted, the minimum is the first element and the maximum is the last. For every pair (i, j), evaluate |arrays[i][0] - arrays[j][-1]| and |arrays[j][0] - arrays[i][-1]|. This works but becomes inefficient when the number of arrays grows large.

Greedy Scan With Running Global Extremes

Iterate through arrays from left to right while tracking the smallest value and largest value seen in earlier arrays. For each new array, compute two candidate distances: the difference between its maximum and the global minimum, and the difference between the global maximum and its minimum. These comparisons guarantee numbers come from different arrays because the stored extremes only originate from previously processed arrays.

Invariant Validation to Avoid Same Array Picks

After computing distances for the current array, update the running global minimum and maximum using its boundary elements. The invariant is that the stored extremes always belong to earlier arrays only. This ensures every candidate distance uses elements from two different arrays while still capturing the largest possible cross array difference.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Only the first and last elements of each sorted array are used. A single pass over the arrays maintains running minimum and maximum values, so the time complexity is O(m) where m is the number of arrays. Space complexity is O(1) because only a few variables track global extremes and the best distance.

What Interviewers Usually Probe

Recognizes that sorted arrays mean only boundary values influence the maximum distance.
Uses a running minimum and maximum from previously processed arrays.
Explains why updating extremes after computing distances prevents using the same array twice.

Common Pitfalls or Variants

Common pitfalls

Updating the global minimum and maximum before computing distances, which can incorrectly compare values from the same array.
Attempting to compare all internal elements instead of using the sorted boundary property.
Forgetting to check both directions: current max minus global min and global max minus current min.

Follow-up variants

Return the pair of values that produces the maximum distance instead of just the distance.
Modify the problem so arrays are not sorted, requiring preprocessing to find local minima and maxima.
Extend the task to select k arrays and maximize the spread among chosen elements.

FAQ

What is the key greedy idea in Maximum Distance in Arrays?

The greedy insight is that the largest distance must involve the smallest value from one array and the largest value from another. Because arrays are sorted, these values are simply the first and last elements, allowing a running global minimum and maximum to be maintained.

Why do we track extremes only from previous arrays?

Tracking extremes only from earlier arrays guarantees that any comparison with the current array uses elements from two different arrays. This preserves the constraint that both selected numbers cannot come from the same array.

Why are only the first and last elements of each array relevant?

Each array is sorted in ascending order, so the smallest element is at the beginning and the largest at the end. Any larger absolute difference must involve one of these boundaries rather than interior elements.

What is the time complexity of the optimal approach?

The optimal greedy scan processes each array once and performs constant work per array. This results in O(m) time complexity with O(1) extra space.

How does the greedy invariant prevent incorrect distances?

The invariant keeps the global minimum and maximum tied to arrays processed earlier. Distances are computed before updating these values, ensuring the current array never compares its own elements against itself.

terminal

Solution

Solution 1: 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 $\textit{mi}$ and $\textit{mx}$, representing the minimum and maximum values of the arrays we have traversed. Initially, $\textit{mi}$ and $\textit{mx}$ are the first and last elements of the first array, respectively.

class 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

Continue Practicing

#621 task scheduler #630 course schedule iii #632 smallest range covering elements from k lists