{x}
blog image

Maximum Distance in Arrays

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.

Solution Explanation for LeetCode 624: Maximum Distance in Arrays

This problem asks to find the maximum absolute difference between any two numbers from different arrays in a given list of sorted arrays. The optimal solution leverages the fact that the arrays are sorted. We only need to consider the minimum and maximum values within each array.

Approach

The core idea is to iterate through the arrays, keeping track of the global minimum (mi) and maximum (mx) values encountered so far. For each array, we calculate the maximum distance that can be achieved using its minimum and maximum elements with the current mi and mx. We update mi and mx as we progress.

Algorithm:

  1. Initialization: Initialize mi and mx with the minimum and maximum values from the first array. Initialize ans (maximum distance) to 0.

  2. Iteration: Iterate through the remaining arrays (from the second array onwards).

    • For each array, calculate two potential maximum distances:
      • a = abs(arr[0] - mx): The distance between the minimum element of the current array and the global maximum.
      • b = abs(arr[-1] - mi): The distance between the maximum element of the current array and the global minimum.
    • Update ans to the maximum of ans, a, and b.
    • Update mi to the minimum of mi and the current array's minimum.
    • Update mx to the maximum of mx and the current array's maximum.

  3. Return: Return ans, which holds the overall maximum distance found.

Time and Space Complexity

  • Time Complexity: O(m*k), where 'm' is the number of arrays and 'k' is the maximum length of any array. In the worst case, we need to iterate through each array once. However, since we only access the first and last elements of each array, the complexity is closer to O(m). The reduce solution is also O(m).

  • Space Complexity: O(1). The solution uses a constant amount of extra space to store variables like mi, mx, and ans.

Code Examples (Python, Java, C++, Go, TypeScript, JavaScript)

The code examples in various languages provided earlier in the response follow this approach. They all perform the same steps: initialization, iteration with distance calculations and updates, and finally returning the maximum distance. The one-line reduce solution is concise but functionally equivalent to the iterative approach.

Example Walkthrough (Python)

Let's trace the Python code with the input arrays = [[1,2,3],[4,5],[1,2,3]]:

  1. mi = 1, mx = 3, ans = 0.
  2. Iterate through [4, 5]:
    • a = abs(4 - 3) = 1
    • b = abs(5 - 1) = 4
    • ans = max(0, 1, 4) = 4
    • mi = min(1, 4) = 1
    • mx = max(3, 5) = 5
  3. Iterate through [1, 2, 3]:
    • a = abs(1 - 5) = 4
    • b = abs(3 - 1) = 2
    • ans = max(4, 4, 2) = 4
    • mi = min(1, 1) = 1
    • mx = max(5, 3) = 5
  4. Return ans = 4.

This walkthrough demonstrates how the algorithm efficiently finds the maximum distance by only considering the minimum and maximum elements of each array and updating the global minimum and maximum accordingly.