Straightforward AC Java Solution with Explanation


  • 4

    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; // ma](link url)x
            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.


Log in to reply
 

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