LeetCode 624: Maximum Distance in Arrays

Problem Restatement

We are given m arrays. Each array is sorted in ascending order.

We must pick two integers from two different arrays and compute their distance.

The distance between two integers a and b is:

abs(a - b)

Return the maximum possible distance.

For example, from:

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

we can pick 1 from the first array and 5 from the second array. The distance is 4.

The two numbers must come from different arrays. This condition is the main detail of the problem.

Input and Output

Example function shape:

def maxDistance(arrays: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

The answer is:

4

One valid choice is:

1 from [1, 2, 3]
5 from [4, 5]

The distance is:

abs(1 - 5) == 4

Example 2:

arrays = [[1], [1]]

The only possible distance is:

abs(1 - 1) == 0

So the answer is:

0

Example 3:

arrays = [[1, 4], [0, 5]]

A tempting answer is:

5 - 0 == 5

But both 0 and 5 are in the second array.

That is not allowed.

The best valid answer is:

max(abs(1 - 5), abs(4 - 0)) == 4

First Thought: Check Every Pair of Arrays

Since the two numbers must come from different arrays, we can compare every pair of arrays.

Because each array is sorted, the smallest value is at index 0, and the largest value is at index -1.

For two arrays A and B, the best distance between them must be one of:

abs(A[0] - B[-1])
abs(B[0] - A[-1])

So we could check every pair of arrays and keep the best answer.

This works, but if there are many arrays, checking every pair is too slow.

If there are m arrays, this takes O(m^2) time.

Key Insight

When we scan arrays from left to right, we only need to remember two values from previous arrays:

For the current array arr, the best distance using this array and a previous array is one of:

arr[-1] - min_so_far

or:

max_so_far - arr[0]

This works because the current array is sorted.

Its smallest value is arr[0].

Its largest value is arr[-1].

The previous arrays are represented by their best possible minimum and maximum endpoints.

The important detail is update order.

We compute the answer first, then update min_so_far and max_so_far.

That ensures the two selected values come from different arrays.

Algorithm

Initialize using the first array:

min_so_far = arrays[0][0]
max_so_far = arrays[0][-1]
answer = 0

Then scan from the second array onward.

For each arr:

1. Let current_min = arr[0].
2. Let current_max = arr[-1].
3. Try pairing the current maximum with the previous minimum.
4. Try pairing the previous maximum with the current minimum.
5. Update the answer.
6. Update min_so_far.
7. Update max_so_far.

The update step is:

answer = max(
    answer,
    current_max - min_so_far,
    max_so_far - current_min,
)

Then:

min_so_far = min(min_so_far, current_min)
max_so_far = max(max_so_far, current_max)

Correctness

Each array is sorted, so the maximum distance between a value from one array and a value from another array must use an endpoint: either the smaller endpoint of one array or the larger endpoint of the other array.

When processing a current array, min_so_far is the smallest value available from all earlier arrays, and max_so_far is the largest value available from all earlier arrays.

For the current array, its largest value is current_max. The best distance where the current array contributes the larger value is therefore:

current_max - min_so_far

Its smallest value is current_min. The best distance where the current array contributes the smaller value is therefore:

max_so_far - current_min

The algorithm checks both possibilities, so it considers the best valid distance involving the current array and any previous array.

The algorithm updates min_so_far and max_so_far only after checking the current array. Therefore, the current array is never paired with itself.

Every valid pair of arrays has one array that appears later in the scan. When that later array is processed, the earlier array is already represented by min_so_far or max_so_far. Therefore, the algorithm considers the best distance for every valid pair.

Thus the final answer is the maximum possible distance.

Complexity

Here, m is the number of arrays.

The total number of integers can be large, but we do not scan inside each array.

Implementation

from typing import List

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        min_so_far = arrays[0][0]
        max_so_far = arrays[0][-1]
        answer = 0

        for arr in arrays[1:]:
            current_min = arr[0]
            current_max = arr[-1]

            answer = max(
                answer,
                current_max - min_so_far,
                max_so_far - current_min,
            )

            min_so_far = min(min_so_far, current_min)
            max_so_far = max(max_so_far, current_max)

        return answer

Code Explanation

We initialize from the first array:

min_so_far = arrays[0][0]
max_so_far = arrays[0][-1]

This gives us valid previous values before processing the second array.

The answer starts at 0:

answer = 0

Distances are never negative, so this is safe.

For each later array, we read only its endpoints:

current_min = arr[0]
current_max = arr[-1]

Then we try the two possible extreme pairings:

current_max - min_so_far
max_so_far - current_min

We update the answer with the best value found so far:

answer = max(answer, current_max - min_so_far, max_so_far - current_min)

Only after that do we update the global endpoints:

min_so_far = min(min_so_far, current_min)
max_so_far = max(max_so_far, current_max)

This order prevents pairing two values from the same array.

Testing

def run_tests():
    s = Solution()

    assert s.maxDistance([[1, 2, 3], [4, 5], [1, 2, 3]]) == 4
    assert s.maxDistance([[1], [1]]) == 0
    assert s.maxDistance([[1, 4], [0, 5]]) == 4
    assert s.maxDistance([[-5, -4], [0, 1], [3, 10]]) == 15
    assert s.maxDistance([[0, 10], [1, 2], [3, 4]]) == 9
    assert s.maxDistance([[1], [2], [3], [4]]) == 3

    print("all tests passed")

run_tests()

Test meaning: