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

• 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;
}
};
``````

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