Problem Statement 624. 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.

My Thought Process

As the subarrays are sorted in ascending order, the first element will always be smallest and the last element will always be the largest. I came up with below algorithm:

1. Mark the first element of the first subarray as min. and the last element of the first subarray as max.
2. iterate over the array and check if the current subarray's first element is smaller than our min and the last element of the current subarray is higher than our max. replace min and max accordingly.
3. return the difference between max and min.

My algorithm mainly succeeded but failed for the test case like below.

[[1,4],[0,5]]

as you can see for our algorithm we are replacing min and max based on the current subarray and if both min and max elements exist in the same array we are returning incorrect answers as the problem statement specifically asks to choose elements from 2 Different arrays.

I updated my algorithm as below:

1. Mark the first element of the first subarray as min. and the last element of the first subarray as max.
2. iterate over the array and mark the current subarray's first element as localMin and the last element as localMax.
3. find the difference between localMax and min, the difference between max and localMin. this will give us 2 absolute differences between 2 separate subarrays. i.e. for [[1,2,3],[4,5]] this will be 4 and 1 respectively we need to select the maximum difference between these 2.
4. find the maximum between the above calculated max difference and the previously calculated result. set the result to whichever is higher.
5. return the result.

Output

Time and Space complexity

Time Complexity: we iterate over all the elements in the array and can directly access the first and last elements and don't need to iterate inside the subarrays. so the time complexity will be O(n)

Space Complexity: O(1) as we do not need any additional space.