5-liner C++ and Python O(m) simple solution, O(1) space


  • 4

    Because each array is sorted, just need to consider the first and last elements in each array.

    When you scan another array a, the answer maxDif is simply given by

    maxDif = max(maxDif, max(a.back()-curMin, curMax-a.front()));
    

    where curMin and curMax are current min and max values in all previous arrays.

        int maxDistance(vector<vector<int>>& arrays) {
            int maxDif = 0, curMin = 10000, curMax = -10000;
            for (auto& a : arrays) {
                maxDif = max(maxDif, max(a.back()-curMin, curMax-a.front()));
                curMin = min(curMin, a.front()), curMax = max(curMax, a.back());
            }
            return maxDif;
        }
    

    Python:

        def maxDistance(self, arrays):
            res, curMin, curMax = 0, 10000, -10000
            for a in arrays :
                res = max(res, max(a[-1]-curMin, curMax-a[0]))
                curMin, curMax = min(curMin, a[0]), max(curMax, a[-1])
            return res
    

Log in to reply
 

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