# Maximum Distance in Arrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-distance-in-arrays)
Canonical: https://scaleengineer.com/dsa/problems/maximum-distance-in-arrays
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
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 <= 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.

# Approaches
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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.

```java
import java.util.List;

class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int maxDist = 0;
        for (int i = 0; i < arrays.size(); i++) {
            for (int j = i + 1; j < arrays.size(); j++) {
                List<Integer> list1 = arrays.get(i);
                List<Integer> list2 = arrays.get(j);
                
                int min1 = list1.get(0);
                int max1 = list1.get(list1.size() - 1);
                
                int min2 = list2.get(0);
                int max2 = list2.get(list2.size() - 1);
                
                maxDist = Math.max(maxDist, Math.abs(max2 - min1));
                maxDist = Math.max(maxDist, Math.abs(max1 - min2));
            }
        }
        return maxDist;
    }
}
```
### 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`.

## Single Pass Approach
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.
**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.
**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.
### Explanation
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.

```java
import java.util.List;

class Solution {
    public int maxDistance(List<List<Integer>> arrays) {
        int maxDist = 0;
        
        // Initialize min and max with the first array's values
        List<Integer> firstList = arrays.get(0);
        int minVal = firstList.get(0);
        int maxVal = firstList.get(firstList.size() - 1);
        
        // Iterate from the second array
        for (int i = 1; i < arrays.size(); i++) {
            List<Integer> currentList = arrays.get(i);
            int currentMin = currentList.get(0);
            int currentMax = currentList.get(currentList.size() - 1);
            
            // Calculate max distance with the current array and the values from previous arrays
            maxDist = Math.max(maxDist, Math.abs(currentMax - minVal));
            maxDist = Math.max(maxDist, Math.abs(maxVal - currentMin));
            
            // Update the overall min and max values seen so far
            minVal = Math.min(minVal, currentMin);
            maxVal = Math.max(maxVal, currentMax);
        }
        
        return maxDist;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ; } }
```

### JavaScript

```javascript
/** * @param {number[][]} arrays * @return {number} */ var maxDistance =
  function (arrays) {
    const n = arrays.length;
    let res = 0;
    let [min, max] = [Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY];
    for (let i = 0; i < n; i++) {
      const a = arrays[i];
      res = Math.max(Math.max(a.at(-1) - min, max - a[0]), res);
      min = Math.min(min, a[0]);
      max = Math.max(max, a.at(-1));
    }
    return res;
  };

```

### CPP

```cpp
class 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 ; } };
```

### Python

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