Java O(n), one scan


  • 0
    A
    public class Solution {
        public int maxDistance(List<List<Integer>> arrays) {
            // algorithm 2017/06/18: slightly smarter algo is to sort all the mins and maxs.
            // If the min of mins and max of maxs do not belong to the same array, then the distance between min of mins and max of maxs is the result
            // Otherwise, the result is the max of the following:
            // 1. min of mins and 2nd max of maxs
            // 2. second min of mins and max of maxs
            int countArrays     = arrays.size();
            int minOfMins       = Integer.MAX_VALUE;
            int minOfMinsAsIndex = -1;
            int secondMinOfMins = Integer.MAX_VALUE;
            int maxOfMaxs       = Integer.MIN_VALUE;
            int secondMaxOfMaxs = Integer.MIN_VALUE;
            int minOfMinsAtIndex = -1;
            int maxOfMaxsAtIndex = -1;
    
            for (int index = 0; index < countArrays; index++) {
                List<Integer> array = arrays.get(index);
                int min = array.get(0);
                int max = array.get(array.size()-1);
                if (min < minOfMins) {
                    secondMinOfMins  = minOfMins;       // remember to shift to secondMinOfMins
                    minOfMins        = min;
                    minOfMinsAtIndex = index;
                } else if (min < secondMinOfMins) {
                    secondMinOfMins  = min;
                }
    
                if (max > maxOfMaxs) {
                    secondMaxOfMaxs  = maxOfMaxs;
                    maxOfMaxs        = max;
                    maxOfMaxsAtIndex = index;
                } else if (max == maxOfMaxs) {
                    // try our best to make minOfMins occurred in a different array of maxOfMaxs
                    if (index != minOfMinsAtIndex) {
                        maxOfMaxsAtIndex = index;
                    }
                } else if (max > secondMaxOfMaxs) {
                    secondMaxOfMaxs  = max;
                }
            }
    
            if (minOfMinsAtIndex != maxOfMaxsAtIndex) {
                return Math.abs(minOfMins - maxOfMaxs);
            } else {
                return Math.max(Math.abs(minOfMins - secondMaxOfMaxs), Math.abs(maxOfMaxs - secondMinOfMins));
            }
        }
    }

Log in to reply
 

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