Java O(n): Finding min and max twice


  • 0
    L

    Firstly, find the min and max values from the 2-D array.
    Secondly, find the min and max values which are not in the array of previously found min and max.

    Return the max difference between them.

    Remember, we need to return the max diff from two arrays and thus running min max only once might give us elements from the same array.

    public int maxDistance(int[][] arrays) {
    
    	int p1 = -1, p2 = -1;
    	int min1, min2, max1, max2;
    	min1 = min2 = 10001;
    	max1 = max2 = -10001;
    
    	int len1 = arrays.length;
    
    	for (int i = 0; i < len1; i++) {
    		int[] arr = arrays[i];
    		int len2 = arr.length;
    
    		if (arr[0] < min1) {
    			min1 = arr[0];
    			p1 = i;
    		}
    
    		if (arr[len2 - 1] > max2) {
    			max2 = arr[len2 - 1];
    			p2 = i;
    		}
    	}
    
    	for (int i = 0; i < len1; i++) {
    		int[] arr = arrays[i];
    		int len2 = arr.length;
    
    		if (arr[len2 - 1] > max1 && i != p1) {
    			max1 = arr[len2 - 1];
    		}
    
    		if (arr[0] < min2 && i != p2) {
    			min2 = arr[0];
    		}
    	}
    
    	return Math.max(Math.abs(max1 - min1), Math.abs(max2 - min2));
    }

Log in to reply
 

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