624. Maximum Distance in Arrays

[mah-shamim]

Topics: Array, Greedy

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.

[topugit]

We need to calculate the maximum possible distance between two integers, each picked from different arrays. The key observation is that the maximum distance will most likely be between the minimum value of one array and the maximum value of another array.

To solve this problem, we can follow these steps:

1. Track the minimum value and maximum value as you iterate through the arrays.
2. For each array, compute the potential maximum distance by comparing the current array's minimum with the global maximum and the current array's maximum with the global minimum.
3. Update the global minimum and maximum as you proceed.

Let's implement this solution in PHP: 624. Maximum Distance in Arrays

<?php
function maxDistance($arrays) {
    $min_value = $arrays[0][0];
    $max_value = end($arrays[0]);
    $max_distance = 0;
    
    for ($i = 1; $i < count($arrays); $i++) {
        $current_min = $arrays[$i][0];
        $current_max = end($arrays[$i]);
        
        // Calculate distance with the current min and global max
        $max_distance = max($max_distance, abs($current_max - $min_value));
        
        // Calculate distance with the current max and global min
        $max_distance = max($max_distance, abs($max_value - $current_min));
        
        // Update global min and max
        $min_value = min($min_value, $current_min);
        $max_value = max($max_value, $current_max);
    }
    
    return $max_distance;
}

// Example usage:
$arrays1 = [[1,2,3],[4,5],[1,2,3]];
echo maxDistance($arrays1); // Output: 4

$arrays2 = [[1],[1]];
echo maxDistance($arrays2); // Output: 0
?>

Explanation:

• min_value and max_value are initialized with the first array’s minimum and maximum values.
• As we iterate through each array starting from the second one:
  • We calculate the distance by comparing the global minimum with the current array’s maximum and the global maximum with the current array’s minimum.
  • Update the max_distance whenever a larger distance is found.
  • Update min_value and max_value to reflect the minimum and maximum values encountered so far.
• Finally, the function returns the maximum distance found.

This solution runs in O(m) time, where m is the number of arrays, making it efficient given the problem constraints.

[mah-shamim]

thanks to solve the "Maximum Distance in Arrays" problem