Java Solution,Traverse only Once, O(n) Time with Explanation


  • 0
    F

    The purpose is to find min d(ak,q)+d(ak,t)+2*sum{d(ai,t),i!=k}, which is equal to 2*sum{d(ai,t),all i}+d(ak,q)-d(ak,t), so we only need to find min{d(ak,q)-d(ak,t)}.

    d(ai,t) is the distance of nuts[i] to tree, d(ai,q) is the distance of nuts[i] to squirrel.

        public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        	int[] d=new int[nuts.length];//distance of nuts to tree 
        	int minDiff=Integer.MAX_VALUE;
        	int result=0;
        	for (int i = 0; i < nuts.length; i++) {
        		d[i]=Math.abs(nuts[i][0]-tree[0])+Math.abs(nuts[i][1]-tree[1]);
    			int disSqui=Math.abs(nuts[i][0]-squirrel[0])+Math.abs(nuts[i][1]-squirrel[1]);//distance of nut to squirrel
    			int diff=disSqui-d[i];
    			if(diff<minDiff){
    				minDiff=diff;
    			}
    			result+=(2*d[i]);
    		}
        	result+=minDiff;
        	return result;
        }
    

Log in to reply
 

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