# Straightforward AC Java Solution with Explanation

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

• @wxl163530 Needs to check if an array is empty or not.
You can change for loops to check this condition like this:
for(int i =0; i<a.length && a[i].length > 0 ;i++)

• I don't think @shawngao 's solution is more efficient. Anyway, in his solution, though there is only one `for` loop, there are four comparisons in each pass. Here, in your solution, in the worst case, we need to find the 1st min, 2nd min and 1st max and 2nd max, which are just separated in 4 `for` loops. However, in each `for` loop we need only one comparison.

Therefore, I think @shawngao 's and your solution are of the same time complexity `O(m)` and the constant should be also very similar, about 4. I have the same idea with you and the Python implementation is:

``````class Solution(object):
def maxDistance(self, arrays):
"""
:type arrays: List[List[int]]
:rtype: int
"""
# find the 1st min and 1st max along with their associated array indices in arrays
min1, imin1 = min((array[0], i) for i, array in enumerate(arrays))
max1, imax1 = max((array[-1], i) for i, array in enumerate(arrays))
if imin1 != imax1:
return max1 - min1
# find the 2nd min and 2nd max
min2 = min(array[0] for i, array in enumerate(arrays) if i != imin1)
max2 = max(array[-1] for i, array in enumerate(arrays) if i != imax1)
return max(max2 - min1, max1 - min2)``````

• But what if there are multiple arrays that contains the min number? You will only remember the index of first array of min number. But depends one which array you exclude in next phase, the second largest number might be different.

• This is very similar to my own first solution. The running time is a little embarrassing though compared with the optimal solution. Posting my code here.

``````
public class Solution {
public int maxDistance(List<List<Integer>> arrays) {
List<List<Integer>> res = new ArrayList<>();
int n = arrays.size();
int minMin = Integer.MAX_VALUE, maxMax = Integer.MIN_VALUE;
List<Integer> lsMin = new ArrayList<>();
List<Integer> lsMax = new ArrayList<>();
for (List<Integer> ls : arrays) {
int index = arrays.indexOf(ls);
int thisMin = ls.get(0), thisMax = ls.get(ls.size() - 1);
if (thisMin < minMin) {
minMin = thisMin;
lsMin.clear();
} else if (thisMin == minMin) {
}
if (thisMax > maxMax) {
maxMax = thisMax;
lsMax.clear();
} else if (thisMax == maxMax) {
}
}
int accum = 0;
for (int i : lsMin) accum ^= i;
for (int i : lsMax) accum ^= i;
if (accum != 0 || (accum == 0 && lsMin.size() > 1)) return maxMax - minMin;
//minMin and maxMax in same list: either one of them will be in the maximum distance
int avoidIndex = lsMin.get(0);
int secondMin = Integer.MAX_VALUE, secondMax = Integer.MIN_VALUE;
for (int i = 0; i < arrays.size(); i++) {
if (i == avoidIndex) continue;
List<Integer> ls = arrays.get(i);
int thisMin = ls.get(0), thisMax = ls.get(ls.size() - 1);
if (thisMin < secondMin) secondMin = thisMin;
if (thisMax > secondMax) secondMax = thisMax;
}
return Math.max(Math.abs(maxMax - secondMin), Math.abs(minMin - secondMax));
}
}
``````

If it is at all possible for the global `min` and global `max` to not occur in the same list(considering duplicates), then the `max distance` is just `abs(max-min)`.
But if not, we find the `secondMin` and the `secondMax`, and the `max distance` must involve at least one of `min` and `max`. This solution has bad running time, just posting here for fun.

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