LeetCode Daily Question 16/08/2024 - 624. Maximum Distance in Arrays

Problem Description:

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

from typing import List
class Solution:
  def maxDistance(self, arrays: List[List[int]]) -> int:
    max_elt, min_elt = float('-inf'), float('inf')
    max_index, min_index = -1
    for i, array in enumerate(arrays):
      if array[0] < min_elt:
        min_elt = array[0]
        min_index = i
      if array[-1] > max_elt:
        max_elt = array[-1]
        max_index = i
    
    if max_index != min_index:
      return abs(max_elt - min_elt)
   	
    second_max, seoncd_min = float('-inf'), float('inf')
    for i, array in enumerate(arrays):
      if i != min_index:
        second_min = min(second_min, array[0])
      if i != max_index:
        seoncd_max = max(seoncd_max, array[-1])
      
    return max(abs(max_elt - second_min), abs(second_max - min_elt))

Explanation:

To solve this question, we find the maximum distance by keep track of the global min and max.

The catch of this problem is when both the global min and global max exists in the same array.

To avoid this we need to keep track of the indices of global min and global max, and if they are the same, we have to find the second min and second max to ensure the min and max are chosen from different arrays.

So we begin by finding the global min and max and their respective index.

max_elt, min_elt = float('-inf'), float('inf')
max_index, min_index = -1
for i, array in enumerate(arrays):
  if array[0] < min_elt:
    min_elt = array[0]
    min_index = i
  if array[-1] > max_elt:
    max_elt = array[-1]
    max_index = i

If min_index and max_index are distinct, then we have found the max distance.

if max_index != min_index:
  return abs(max_elt - min_elt)

Otherwise, we need to keep track of a second min and second max. We also need to ensure that these min and max lives within a distinct array from the global max and min we found. This ensures that our max_distance is valid within the constraints of the question.

second_max, second_min = float('-inf'), float('inf')
for i, array in enumerate(arrays):
  if i != min_index:
    second_min = min(second_min, array[0])
  if i != max_index:
    second_max = max(second_max, array[-1])

Finally, we calculate the max distance by taking max of the differences between global max and second min, and second max and global min

return max(abs(max_elt - second_min), abs(second_max - min_elt))

The time complexity is O(n) as we have to traverse the entire array to find the global min max and their indices. The space complexity is O(1) as we only store single-valued variables in memory.

The full solution can be found near the top of the page.