624. Maximum Distance in Arrays - Explanation

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

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

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

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$