Problem statement

https://leetcode.com/problems/maximum-distance-in-arrays/

Solution 1

My idea was to find two smallest and two biggest numbers, and we can do it, but we need to be careful: handle border cases, where we have equal numbers and also the case when smallest and biggest point are from the same array.

Complexity

Time complexity is O(m), where m is total number of numbers. space is O(1).

Code

class Solution:
    def maxDistance(self, arrs: List[List[int]]) -> int:
        m1, m2 = -float("inf"),  -float("inf")
        l1, l2 =  float("inf"),   float("inf")
        max_len = 0
        
        for ind in range(len(arrs)):
            max_len = max(max_len, arrs[ind][-1] - arrs[ind][0])
            for i in [arrs[ind][0], arrs[ind][-1]]:
                [m1, m2] = sorted([m1, m2, i])[1:]
                [l1, l2] = sorted([l1, l2, i])[:2]
                
        return max(m1-l1, m2-l2) if max_len == m2-l1 else m2-l1

Solution 2

There is more beautiful solution: let us keep current min and max. For each new array we update min and max and also we update our ans: distance between maximum and beginning of array and distance between minimum and ending of array.

Complexity

Time complexity is O(m), space complexity is O(1).

Code

class Solution:
    def maxDiff(self, arrs):
        ans, curMin, curMax = 0, arrs[0][0], arrs[0][-1]
        for array in arrs[1:]:
            ans = max(abs(array[-1]-curMin), abs(curMax-array[0]), ans)
            curMin = min(curMin, array[0])
            curMax = max(curMax, array[-1])
        return ans