LeetCode 624: Maximum Distance in Arrays

Problem Description

LeetCode Problem 624

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.

Difficulty: Medium

Tags: array, greedy

Rating: 92.67%

Intuition

Since we’re looking for the maximum absolute difference between two numbers, and each array is sorted, we can make two key observations:

1. The maximum difference will always involve either:

   • The minimum value from one array and the maximum value from another array
   • Or the maximum value from one array and the minimum value from another array

2. Since arrays are sorted, we only need to look at:

   • The first element of each array (minimum value)
   • The last element of each array (maximum value)

Solution Approach

Here’s the solution with detailed explanations:

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        # Initialize min and max from the first array
        imin, imax = arrays[0][0], arrays[0][-1]
        res = 0
        
        # Iterate through remaining arrays
        for i in range(1, len(arrays)):
            curmin, curmax = arrays[i][0], arrays[i][-1]
            
            # Calculate maximum possible distance using current array
            # and previous min/max values
            res = max(res,
                     abs(imax - curmin),  # Previous max - current min
                     abs(curmax - imin))  # Current max - previous min
            
            # Update global min and max for next iterations
            imax = max(imax, curmax)
            imin = min(imin, curmin)
        
        return res

How the Algorithm Works

Let’s break down the solution step by step:

1. Initialization:

   • Start with the first array’s minimum and maximum values
   • Initialize result variable to track maximum distance

2. Main Loop:

   • For each subsequent array, we: a. Get its minimum and maximum values b. Calculate two possible distances:
     • Distance between previous maximum and current minimum
     • Distance between current maximum and previous minimum c. Update our running maximum distance if needed d. Update global minimum and maximum for future comparisons

3. Final Result:

   • Return the maximum distance found

Why This Works

The solution is correct because:

1. We never compare numbers within the same array (we always use values from different arrays)
2. By tracking global minimum and maximum values, we ensure we don’t miss any potential maximum differences
3. The greedy approach works because we only need the endpoints of each sorted array

Complexity Analysis

• Time Complexity: $O(n)$, where n is the number of arrays

  • We only look at each array once
  • For each array, we only access its first and last elements

• Space Complexity: $O(1)$

  • We only use a constant amount of extra space regardless of input size