My Java O(n) Solution: find min/max twice but in a round.


  • 0
    public int maxDistance(int[][] arrays) {
        int n = arrays.length;
        int[][] min = { {Integer.MAX_VALUE, 0},{Integer.MAX_VALUE, 0}};
        int[][] max = { {Integer.MIN_VALUE, 0},{Integer.MIN_VALUE, 0}};
        for(int i=0;i<n;++i) {
            int m = arrays[i].length;
            int minC = arrays[i][0];
            int maxC = arrays[i][m-1];
            if(minC <= min[1][0]) {
                if(minC <= min[0][0]) {
                    min[1][0] = min[0][0];
                    min[1][1] = min[0][1];
                    min[0][0] = minC;
                    min[0][1] = i;
                } else {
                    min[1][0] = minC;
                    min[1][1] = i;
                }
            }
            if(maxC >= max[1][0]) {
                if(maxC >= max[0][0]) {
                    max[1][0] = max[0][0];
                    max[1][1] = max[0][1];
                    max[0][0] = maxC;
                    max[0][1] = i;
                } else {
                    max[1][0] = maxC;
                    max[1][1] = i;
                }
            }
        }
        if(min[0][1] != max[0][1]) {
            return Math.abs(max[0][0]-min[0][0]);
        }
        return Math.max(Math.abs(max[0][0]-min[1][0]),Math.abs(max[1][0]-min[0][0]));
    }

Log in to reply
 

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