# 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:

```python
abs(a - b)
```

Return the maximum possible distance.

For example, from:

```python
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

| Item | Meaning |
|---|---|
| Input | A list of sorted integer arrays |
| Output | The maximum distance between two numbers from different arrays |
| Distance | `abs(a - b)` |
| Important rule | The two chosen numbers must come from different arrays |

Example function shape:

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

## Examples

Example 1:

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

The answer is:

```python
4
```

One valid choice is:

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

The distance is:

```python
abs(1 - 5) == 4
```

Example 2:

```python
arrays = [[1], [1]]
```

The only possible distance is:

```python
abs(1 - 1) == 0
```

So the answer is:

```python
0
```

Example 3:

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

A tempting answer is:

```python
5 - 0 == 5
```

But both `0` and `5` are in the second array.

That is not allowed.

The best valid answer is:

```python
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:

```python
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:

| Value | Meaning |
|---|---|
| `min_so_far` | The smallest first element among previous arrays |
| `max_so_far` | The largest last element among previous arrays |

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

```python
arr[-1] - min_so_far
```

or:

```python
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:

```python
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:

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

Then:

```python
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:

```python
current_max - min_so_far
```

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

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m)` | We inspect only the first and last element of each array |
| Space | `O(1)` | We keep only a few variables |

Here, `m` is the number of arrays.

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

## Implementation

```python
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:

```python
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`:

```python
answer = 0
```

Distances are never negative, so this is safe.

For each later array, we read only its endpoints:

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

Then we try the two possible extreme pairings:

```python
current_max - min_so_far
max_so_far - current_min
```

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

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

Only after that do we update the global endpoints:

```python
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

```python
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:

| Test | Why |
|---|---|
| `[[1,2,3],[4,5],[1,2,3]]` | Official-style basic case |
| `[[1],[1]]` | Minimum distance is zero |
| `[[1,4],[0,5]]` | Prevents using min and max from same array |
| Negative values | Checks signed numbers |
| First array has both extremes | Ensures different-array rule is preserved |
| Single-element arrays | Checks endpoint logic still works |