Python, Straightforward with Explanation


  • 0

    Say we use elements x, y contributing to our final answer abs(x - y) from two different arrays x ∈ arrays[i] and y ∈ arrays[j] with i < j.

    There are two cases: if x >= y, then we choose y = arrays[j][0] and x = (largest value in any array before arrays[j]). If x <= y, then we choose y = arrays[j][-1] and x = (smallest value in any array before arrays[j]).

    This motivates us to maintain mi = (the minimum value seen so far) and ma = (the maximum value seen so far). For each j, we can check if abs(ma - arrays[j][0]) or abs(arrays[j][-1] - mi) would be a better answer.

    def maxDistance(self, arrays):
        mi = arrays[0][0]
        ma = arrays[0][-1]
        ans = 0
        for A in arrays[1:]:
            lo, hi = A[0], A[-1]
            ans = max(ans, abs(ma - lo), abs(hi - mi))
            mi = min(mi, lo)
            ma = max(ma, hi)
        return ans
    

  • 0

    @awice I like your post, thank you for your posting your code!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.