O(N) time O(1) space one pass w/ short C++ & Python solutions


  • 3
    Z

    we can treat each array as an interval, to find the max abs diff, we just need to compare the start and end with each other

    python solution:

    class Solution(object):
        def maxDistance(self, arrays):
            result, start, end = 0, arrays[0][0], arrays[0][-1]
            for i in xrange(1, len(arrays)):
                result = max(result, abs(arrays[i][0] - end))
                result = max(result, abs(arrays[i][-1] - start))
                start = min(start, arrays[i][0])
                end = max(end, arrays[i][-1])
            return result
    

    c++ solution:

    class Solution {
    public:
        int maxDistance(vector<vector<int>>& arrays) {
            int result = 0, start = arrays[0][0], end = arrays[0].back();
            for ( int i = 1, n = arrays.size(); i < n; ++i ) {
                result = max(result, abs(arrays[i].back() - start));
                result = max(result, abs(arrays[i][0] - end));
                start = min(start, arrays[i][0]);
                end = max(end, arrays[i].back());
            }
            return result;
        }
    };
    

    Discuss: This problem is tagged with Hash Table, but I don't find a proper way to do it, only c++ seems ok because it has sorted map... this solution is a bit slow and cost more space

    class Solution {
    public:
        int maxDistance(vector<vector<int>>& arrays) {
            int result = 0;
            map<int, int> starts;
            for ( auto && A : arrays )
                ++starts[A[0]];
            for ( auto && A : arrays ) {
                if ( --starts[A[0]] == 0 )
                    starts.erase(A[0]);
                result = max(result, abs(A[0] - starts.begin()->first));
                result = max(result, abs(A.back() - starts.begin()->first));
                ++starts[A[0]];
            }
            return result;
        }
    };
    

Log in to reply
 

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