624. Maximum Distance in Arrays - Explanation

Problem Link

Description

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 <= 10^5
• 1 <= arrays[i].length <= 500
• -10^4 <= arrays[i][j] <= 10^4
• arrays[i] is sorted in ascending order.
• There will be at most 10^5 integers in all the arrays.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

We need to find the maximum absolute difference between elements from two different arrays. The naive approach is to compare every element from every array with every element from every other array. This guarantees we find the answer but is slow due to the nested iteration over all elements.

Algorithm

1. Use four nested loops: the outer two select a pair of different arrays, and the inner two select elements from each array.
2. For each pair of elements from different arrays, compute the absolute difference.
3. Track the maximum difference found.
4. Return the result.

class Solution:
    def maxDistance(self, arrays: list[list[int]]) -> int:
        res = 0
        n = len(arrays)
        for i in range(n - 1):
            for j in range(len(arrays[i])):
                for k in range(i + 1, n):
                    for l in range(len(arrays[k])):
                        res = max(res, abs(arrays[i][j] - arrays[k][l]))
        return res

Time & Space Complexity

• Time complexity: $O((n * x)^2)$
• Space complexity: $O(1)$ constant space used

Where $n$ refers to the number of arrays in $arrays$ and $x$ refers to the average number of elements in each array in $arrays$.

---

2. Better Brute Force

Intuition

Since each array is sorted, the minimum is always at the start and the maximum is always at the end. This means we only need to consider the first and last elements of each array. For any pair of arrays, the maximum distance is either |min1 - max2| or |min2 - max1|. This reduces the inner loops to constant time per pair.

Algorithm

1. For each pair of arrays (i, j) where i < j:
   • Compute |array1[0] - array2[last]| and |array2[0] - array1[last]|.
   • Update the maximum distance.
2. Return the maximum distance found.

class Solution:
    def maxDistance(self, arrays: list[list[int]]) -> int:
        res = 0
        n = len(arrays)
        for i in range(n - 1):
            for j in range(i + 1, n):
                array1 = arrays[i]
                array2 = arrays[j]
                res = max(res, abs(array1[0] - array2[-1]))
                res = max(res, abs(array2[0] - array1[-1]))
        return res

Time & Space Complexity

• Time complexity: $O(n^2)$
• Space complexity: $O(1)$ constant space used

Where $n$ is the number of arrays in $arrays$

---

3. Single Scan

Intuition

We can do better by making a single pass. As we scan through the arrays, we maintain the global minimum and maximum seen so far. For each new array, the best distance involving this array is either current_max - global_min or global_max - current_min. After checking, we update our global min and max to include the current array's values.

The key insight is that we compare the current array against all previous arrays implicitly through the running min and max. This guarantees the two elements come from different arrays.

Algorithm

1. Initialize min_val and max_val from the first array.
2. For each subsequent array:
   • Compute the distance using current_last - min_val and max_val - current_first.
   • Update the result with the maximum of these distances.
   • Update min_val and max_val to include the current array's first and last elements.
3. Return the result.

class Solution:
    def maxDistance(self, arrays: list[list[int]]) -> int:
        res = 0
        n = len(arrays[0])
        min_val = arrays[0][0]
        max_val = arrays[0][-1]
        for i in range(1, len(arrays)):
            n = len(arrays[i])
            res = max(res, max(abs(arrays[i][n - 1] - min_val), 
                               abs(max_val - arrays[i][0])))
            min_val = min(min_val, arrays[i][0])
            max_val = max(max_val, arrays[i][n - 1])
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ constant space used

Where $n$ is the number of arrays in $arrays$

---

Common Pitfalls

Selecting Both Elements from the Same Array

The problem requires elements to come from two different arrays. A common mistake is to find the global minimum and maximum across all elements without ensuring they belong to different arrays. For example, if one array contains both the smallest and largest values, using them would violate the constraint. The single scan solution handles this by comparing the current array's values against previously seen min/max values, guaranteeing they come from different arrays.

Forgetting to Use Absolute Difference

Some solutions compute the difference without taking the absolute value. While the optimal solution always involves max - min (which is positive), intermediate calculations or edge cases might produce negative values. Always use abs() or structure your comparisons to ensure you're computing |a - b| rather than just a - b.

Not Exploiting the Sorted Property of Each Array

Each individual array is sorted in ascending order. Failing to recognize this leads to unnecessarily iterating through all elements when only the first (minimum) and last (maximum) elements of each array matter. The brute force solution that checks every pair of elements is correct but inefficient; the optimized approaches leverage the sorted property to achieve linear time.