Problem Description

You are given m arrays where each array is sorted in ascending order. Your task is to pick two integers from two different arrays (one integer from each array) and calculate the distance between them. The distance between two integers a and b is defined as their absolute difference |a - b|.

Your goal is to find and return the maximum distance possible.

For example, if you have arrays [1, 4, 5] and [0, 2], you could pick:

• 5 from the first array and 0 from the second array, giving distance |5 - 0| = 5
• 1 from the first array and 2 from the second array, giving distance |1 - 2| = 1
• And other combinations...

The maximum distance would be 5 in this case.

The key constraint is that the two integers must come from different arrays - you cannot pick both integers from the same array.

Intuition

Since each array is sorted in ascending order, the smallest element is at the beginning and the largest element is at the end of each array. To maximize the distance |a - b|, we want to pick two numbers that are as far apart as possible.

The key insight is that the maximum distance will always involve either:

• The minimum value from one array and the maximum value from another array
• The maximum value from one array and the minimum value from another array

Since arrays are sorted, we only need to consider the first element (minimum) and last element (maximum) of each array.

As we iterate through the arrays, we can keep track of the global minimum and maximum values seen so far. For each new array we encounter:

• We calculate the distance between the current array's minimum (first element) and the global maximum seen so far
• We calculate the distance between the current array's maximum (last element) and the global minimum seen so far
• We update our answer with the maximum of these distances

The reason we update the global minimum and maximum after calculating distances for the current array is crucial - this ensures we're always picking elements from different arrays. We're comparing the current array's elements with the min/max from previously seen arrays, guaranteeing they come from different sources.

This greedy approach works because we're always considering the most extreme values that could give us the maximum distance, and by processing arrays one by one, we naturally avoid picking two elements from the same array.

Learn more about Greedy patterns.

Solution Approach

We implement the solution by maintaining two variables throughout our traversal:

• mi: tracks the minimum value seen so far across all processed arrays
• mx: tracks the maximum value seen so far across all processed arrays

Initialization: We start by initializing mi and mx with the first and last elements of the first array respectively:

• mi = arrays[0][0] (first element of first array)
• mx = arrays[0][-1] (last element of first array)
• ans = 0 (to store the maximum distance)

Main Loop: We iterate through the remaining arrays starting from index 1. For each array arr:

1. Calculate distances with current array:

   • a = abs(arr[0] - mx): Distance between current array's minimum and global maximum
   • b = abs(arr[-1] - mi): Distance between current array's maximum and global minimum

2. Update maximum distance:

   • ans = max(ans, a, b): Keep track of the largest distance found so far

3. Update global min and max:

   • mi = min(mi, arr[0]): Update global minimum if current array has a smaller first element
   • mx = max(mx, arr[-1]): Update global maximum if current array has a larger last element

The order of operations is important here. We calculate distances using the current array's elements against the min/max from previously processed arrays before updating the global min/max. This ensures we never compare elements from the same array.

Time Complexity: O(m) where m is the number of arrays, since we visit each array exactly once.

Space Complexity: O(1) as we only use a constant amount of extra space for variables mi, mx, and ans.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it works.

Given arrays: [[1, 4, 5], [0, 2], [3, 8, 9]]

Initialization:

• Start with the first array [1, 4, 5]
• mi = 1 (first element of first array)
• mx = 5 (last element of first array)
• ans = 0

Iteration 1: Process array [0, 2]

1. Calculate distances:
   • a = |0 - 5| = 5 (current array's min vs global max)
   • b = |2 - 1| = 1 (current array's max vs global min)
2. Update answer:
   • ans = max(0, 5, 1) = 5
3. Update global min/max:
   • mi = min(1, 0) = 0
   • mx = max(5, 2) = 5

Iteration 2: Process array [3, 8, 9]

1. Calculate distances:
   • a = |3 - 5| = 2 (current array's min vs global max from arrays 0 and 1)
   • b = |9 - 0| = 9 (current array's max vs global min from arrays 0 and 1)
2. Update answer:
   • ans = max(5, 2, 9) = 9
3. Update global min/max:
   • mi = min(0, 3) = 0
   • mx = max(5, 9) = 9

Result: The maximum distance is 9, achieved by picking 9 from array [3, 8, 9] and 0 from array [0, 2].

Notice how at each step, we compare the current array's extremes with the min/max values from previously processed arrays, ensuring we always pick elements from different arrays. The algorithm correctly identifies that the maximum distance comes from the largest value in the third array and the smallest value in the second array.

Solution Implementation

Time and Space Complexity

The time complexity is O(m), where m is the number of arrays. The algorithm iterates through the list of arrays exactly once (from index 1 to the end), performing constant-time operations for each array: accessing the first and last elements, computing absolute differences, updating the minimum and maximum values, and comparing values. Since each operation within the loop takes O(1) time and the loop runs m-1 times, the overall time complexity is O(m).

The space complexity is O(1). The algorithm only uses a fixed amount of extra space regardless of the input size. It maintains four variables: ans for storing the maximum distance, mi for the minimum value seen so far, mx for the maximum value seen so far, and temporary variables a and b for intermediate calculations. These variables do not scale with the number of arrays, resulting in constant space usage.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall: Comparing Elements from the Same Array

The most common mistake is accidentally comparing elements from the same array when calculating the maximum distance. This violates the problem's constraint that the two integers must come from different arrays.

Incorrect Approach:

def maxDistance(arrays):
    # WRONG: Collecting all values first
    all_mins = [arr[0] for arr in arrays]
    all_maxs = [arr[-1] for arr in arrays]
  
    # This might pick min and max from the same array!
    return max(all_maxs) - min(all_mins)

Why it fails: Consider arrays = [[1, 5], [3, 4]]

• The incorrect approach would calculate: max(5, 4) - min(1, 3) = 5 - 1 = 4
• But both 5 and 1 come from the first array [1, 5], which is invalid
• The correct answer is 3 (either |5 - 3| = 2 or |1 - 4| = 3)

Pitfall: Updating Min/Max Before Calculating Distances

Another subtle error is updating the global minimum and maximum values before using them to calculate distances with the current array.

Incorrect Order:

def maxDistance(arrays):
    mi = arrays[0][0]
    mx = arrays[0][-1]
    ans = 0
  
    for arr in arrays[1:]:
        # WRONG: Updating before calculating distances
        mi = min(mi, arr[0])
        mx = max(mx, arr[-1])
      
        # Now we might be comparing arr's own elements!
        ans = max(ans, abs(arr[0] - mx), abs(arr[-1] - mi))
  
    return ans

Solution: The correct approach maintains the invariant that when processing array i, the mi and mx values only contain information from arrays 0 through i-1. This ensures we never compare elements from the same array:

def maxDistance(arrays):
    mi = arrays[0][0]
    mx = arrays[0][-1]
    ans = 0
  
    for arr in arrays[1:]:
        # CORRECT: Calculate distances first
        ans = max(ans, abs(arr[0] - mx), abs(arr[-1] - mi))
      
        # Then update for next iteration
        mi = min(mi, arr[0])
        mx = max(mx, arr[-1])
  
    return ans

The key insight is that the order of operations matters: always calculate distances before updating the global tracking variables.