Java O(nuts) Explanation


  • 1
    X
        public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        
        //Distance between each nut and the tree. Since we need to go from Tree to Nut, and Nut to tree, the total steps with be 2 times the distance.
    
        int total = 0;	
        for (int i = 0; i < nuts.length; i++)
        {
        	total = total + 2 * dist(tree, nuts[i]);
        }
        
    //For the first nut, 
    //let a be the distance from Tree to Nut j
    //let b be the distance from Squirrel to Nut j
    //We need to remove a from the total, and add b to the total
    //Therefore we will MINIMIZE the equation (b-a)
    
        int min = Integer.MAX_VALUE;
        int min_index = -1;
        for (int j = 0; j < nuts.length; j++)
        {
        	int cur = dist(squirrel, nuts[j]) - dist(nuts[j], tree);
        	
        	if ( cur < min)
        	{
        		min = cur;
        		min_index = j;
        	}
        }
        
    //We remove a, and add b
        total = total - dist(nuts[min_index], tree) + dist(nuts[min_index], squirrel);
       
        
        return total;
        }
        
        
        public int dist(int[] a, int[] b)
    
        {
        	int a_x =a[0];
        	int a_y =a[1];
        	int b_x =b[0];
        	int b_y =b[1];
        	
        	int out = Math.abs(a_x - b_x) + Math.abs(a_y - b_y);
        	return out;
        }

  • 0
    S

    Upvoted! Thanks for the explanation. First time solving problem, reading your solution really helps! :)

    If possible, it would help if you explained your logic leading up to the solution a little more. Specifically, how did you arrive at your algorithm and why should we minimize (b - a)?


Log in to reply
 

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