Straightforward AC Java Solution with Explanation


  • 6

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

  • 1
    R

    @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++)


  • 0
    S

    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)

  • 0
    T

    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.


  • 0

    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();
                    lsMin.add(index);
                } else if (thisMin == minMin) {
                    lsMin.add(index);
                }
                if (thisMax > maxMax) {
                    maxMax = thisMax;
                    lsMax.clear();
                    lsMax.add(index);
                } else if (thisMax == maxMax) {
                    lsMax.add(index);
                }
            }
            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.


Log in to reply
 

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