LeetCode 624 - Maximum Distance in Arrays

The problem presents a list of m arrays, each individually sorted in ascending order. You are asked to pick one element from two different arrays and compute the absolute difference between these two elements, which is defined as the distance.

leetcodemediumarraygreedy

LeetCode Problem 624

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem presents a list of m arrays, each individually sorted in ascending order. You are asked to pick one element from two different arrays and compute the absolute difference between these two elements, which is defined as the distance. The goal is to find the maximum possible distance between any such pair.

The input represents multiple arrays of integers. Each array is already sorted, which is a key property. The expected output is a single integer, the largest absolute difference obtainable by selecting one element from one array and another from a different array.

Constraints indicate that the total number of integers across all arrays will not exceed 10^5, and the arrays can be quite small individually (as small as length 1). Arrays can contain negative numbers and large positive numbers up to 10^4. This problem guarantees that each array contains at least one integer, but it does not guarantee that all arrays are of equal length.

Important edge cases include arrays with a single element, arrays containing the same numbers, or arrays that span negative and positive numbers. A naive solution that considers all pairs of elements across arrays could be extremely slow due to the upper limit of 10^5 integers, so an optimized approach is necessary.

Approaches

The brute-force approach is straightforward: iterate over all pairs of arrays, then iterate over all elements within these arrays to compute every possible absolute difference. This guarantees correctness but is computationally infeasible because the time complexity is O(N^2) in the worst case, where N is the total number of integers.

The key observation for an optimal solution is that since each array is sorted, the minimum and maximum elements of each array are sufficient to compute the maximum distance with other arrays. Specifically, for each array, the largest possible distance can be achieved by either pairing its smallest element with the maximum of a previously seen array or its largest element with the minimum of a previously seen array. This observation allows us to track only two values as we iterate through the arrays: the global minimum and global maximum seen so far, updating the maximum distance accordingly. This reduces the time complexity to O(m).

Approach Time Complexity Space Complexity Notes
Brute Force O(N^2) O(1) Compare all element pairs across arrays
Optimal O(m) O(1) Track min and max from previous arrays to compute maximum distance

Algorithm Walkthrough

  1. Initialize two variables: min_val as the first element of the first array and max_val as the last element of the first array. These represent the current global minimum and maximum.
  2. Initialize a variable max_distance to zero to store the largest distance found.
  3. Iterate over the remaining arrays starting from the second array.
  4. For the current array, compute the distance between its first element and the current max_val, and the distance between its last element and the current min_val.
  5. Update max_distance with the maximum of the current max_distance and the two distances computed in step 4.
  6. Update min_val to be the smaller of the current min_val and the first element of the current array.
  7. Update max_val to be the larger of the current max_val and the last element of the current array.
  8. Continue this process until all arrays are processed.
  9. Return max_distance.

Why it works: The algorithm works because the maximum distance must involve either the smallest element of one array and the largest element of a different array. By maintaining the global minimum and maximum seen so far, we ensure that all potential maximum distances are considered without redundantly comparing every element pair.

Python Solution

from typing import List

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        min_val = arrays[0][0]
        max_val = arrays[0][-1]
        max_distance = 0
        
        for arr in arrays[1:]:
            max_distance = max(max_distance, abs(arr[-1] - min_val), abs(max_val - arr[0]))
            min_val = min(min_val, arr[0])
            max_val = max(max_val, arr[-1])
        
        return max_distance

Implementation Explanation: We start by initializing min_val and max_val with the first array's minimum and maximum. For each subsequent array, we calculate the two possible maximum distances using the first and last elements and update the global max_distance accordingly. Finally, we update min_val and max_val to include the current array. This ensures that we always have the correct global minimum and maximum for the next iterations.

Go Solution

func maxDistance(arrays [][]int) int {
    minVal := arrays[0][0]
    maxVal := arrays[0][len(arrays[0])-1]
    maxDistance := 0
    
    for i := 1; i < len(arrays); i++ {
        arr := arrays[i]
        maxDistance = max(maxDistance, abs(arr[len(arr)-1]-minVal), abs(maxVal-arr[0]))
        minVal = min(minVal, arr[0])
        maxVal = max(maxVal, arr[len(arr)-1])
    }
    
    return maxDistance
}

func max(a, b, c int) int {
    if a >= b && a >= c {
        return a
    } else if b >= a && b >= c {
        return b
    }
    return c
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Go Implementation Notes: The Go implementation mirrors the Python approach. Helper functions max, min, and abs handle multiple comparisons and absolute value calculation. Go slices are used instead of lists. No special handling for nil slices is needed because the problem guarantees that each array contains at least one element.

Worked Examples

Example 1: arrays = [[1,2,3],[4,5],[1,2,3]]

Step min_val max_val Current array max_distance calculation max_distance update
Start 1 3 - - 0
Array [4,5] 1 3 [4,5] max( 5-1
Update min_val/max_val min(1,4)=1 max(3,5)=5 - - -
Array [1,2,3] 1 5 [1,2,3] max( 3-1

Output: 4

Example 2: arrays = [[1],[1]]

Step min_val max_val Current array max_distance calculation max_distance update
Start 1 1 - - 0
Array [1] 1 1 [1] max( 1-1

Output: 0

Complexity Analysis

Measure Complexity Explanation
Time O(m) Iterate over all arrays once; within each array, only the first and last elements are considered.
Space O(1) Only a few variables are stored; no extra arrays or data structures are needed.

The time complexity is efficient because we do not iterate through all elements within each array, only the first and last. Space is constant because the solution only needs to track global minimum, maximum, and maximum distance.

Test Cases

# provided examples
assert Solution().maxDistance([[1,2,3],[4,5],[1,2,3]]) == 4  # max distance between 1 and 5
assert Solution().maxDistance([[1],[1]]) == 0  # identical single-element arrays

# boundary values
assert Solution().maxDistance([[-10000],[10000]]) == 20000  # max negative to max positive
assert Solution().maxDistance([[1,2,3],[1,2,3],[1,2,3]]) == 2  # all arrays same range

# stress test
arrays = [[i] for i in range(1, 100001)]
assert Solution().maxDistance(arrays) == 99999  # largest possible distance in a large input

# mix negative and positive numbers
assert Solution().maxDistance([[-10,-5,0],[5,10],[1,2,3]]) == 20
Test Why
[[1,2,3],[4,5],[1,2,3]] standard case with multiple arrays
[[1],[1]] single-element arrays
[[-10000],[10000]] extreme negative and positive
[[1,2,3],[1,2,3],[1,2,3]] identical arrays
range(1,100001) stress test for performance
[[-10,-5,0],[5,10],[1,2,3]]