LeetCode 573: Squirrel Simulation

Explanation:

To solve this problem, we need to find the minimum distance for a squirrel to collect all nuts and return back to the tree. The key insight is that the distance for each squirrel to each nut can be precomputed and stored in an array. Then, for each squirrel, we calculate the total distance by summing the distance to the tree and the distance to each nut. We need to find the squirrel that has the minimum total distance.

Algorithm:

1. Precompute and store the distance from each squirrel to each nut and from each nut to the tree.
2. For each squirrel, calculate the total distance by summing the distance to the tree and the distance to each nut.
3. Find the minimum total distance among all squirrels.

Time Complexity: O(n) where n is the number of nuts. Space Complexity: O(n)

:

class Solution {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int totalDistance = 0;
        int maxDiff = Integer.MIN_VALUE;
        
        for (int[] nut : nuts) {
            int distanceToTree = Math.abs(tree[0] - nut[0]) + Math.abs(tree[1] - nut[1]);
            int distanceToSquirrel = Math.abs(squirrel[0] - nut[0]) + Math.abs(squirrel[1] - nut[1]);
            totalDistance += 2 * distanceToTree;
            maxDiff = Math.max(maxDiff, distanceToTree - distanceToSquirrel);
        }
        
        return totalDistance - maxDiff;
    }
}