The max distance must exist in one of these three differences, 1. difference between maximum and minimum, or 2. difference between 2nd maximum(the num that is only smaller than the maximum) or minimum, or 3. difference between maximum or 2nd minimum(the num that is only bigger than the minimum). Therefore, we just need to find these numbers.

Besides, the link below is a more efficient solution by shawngao

https://discuss.leetcode.com/topic/92859/java-solution-min-and-max

```
public class Solution {
public int maxDistance(int[][] a) {
int min = Integer.MAX_VALUE; // max
int max = Integer.MIN_VALUE; // min
int k = 0, m =0;
for(int i =0;i<a.length;i++){
if(a[i][0]<min){
min = a[i][0];
k = i;
}
if(a[i][a[i].length-1]>max){
max = a[i][a[i].length-1];
m = i;
}
}
if(k!=m) return max - min; // if max and min not in same array then return diff
int ndMin = Integer.MAX_VALUE; // 2nd min
for(int i = 0;i<a.length;i++){
if(i==k) continue; // exclude the array with min
ndMin = Math.min(ndMin,a[i][0]);
}
int ndMax = Integer.MIN_VALUE; // 2nd max
for(int i = 0;i<a.length;i++){
if(i==m) continue; // exclude the array with max
ndMax = Math.max(ndMax,a[i][a[i].length-1]);
}
return Math.max(max - ndMin,ndMax - min);
}
}
```