We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Distance in Arrays

Number: 624

Difficulty: Medium

Paid? No

Companies: Yahoo

Problem Description

You are given m sorted arrays (in ascending order). The task is to choose one element from two different arrays such that the absolute difference between these two elements is maximized. Return this maximum distance.

Key Insights

  • Each array is sorted, so the first element is its minimum and the last element is its maximum.
  • The maximum difference is achieved by considering the global minimum from one array and the global maximum from a different array.
  • As you iterate through the arrays, you can update and maintain the global minimum and maximum seen so far to compute candidate distances.
  • Always ensure that you pick values from two different arrays.

Space and Time Complexity

Time Complexity: O(m), where m is the number of arrays. Space Complexity: O(1) extra space (ignoring input storage).

Solution

We iterate through the arrays while maintaining two global variables: one for the minimum value (globalMin) and one for the maximum value (globalMax) encountered from the previous arrays. For the current array, we compute two candidate differences:

  1. The difference between the current array's maximum and the global minimum.
  2. The difference between the global maximum and the current array's minimum. We update the maximum distance found and then update the global minimum and maximum using the current array's endpoints. This approach ensures correct results by always considering elements from different arrays.

Code Solutions

def max_distance(arrays):
    # Initialize global minimum and maximum using the first array's extremes.
    global_min = arrays[0][0]
    global_max = arrays[0][-1]
    max_dist = 0
    
    # Traverse through the arrays starting from the 2nd one.
    for i in range(1, len(arrays)):
        current_first = arrays[i][0]
        current_last = arrays[i][-1]
        # Calculate possible distances from the global extremes.
        max_dist = max(max_dist, abs(current_last - global_min), abs(global_max - current_first))
        # Update global minimum and maximum.
        global_min = min(global_min, current_first)
        global_max = max(global_max, current_last)
    
    return max_dist

# Example usage:
print(max_distance([[1,2,3],[4,5],[1,2,3]]))  # Output: 4
← Back to All Questions