Leetcode 573. Squirrel Simulation

You are given two integers height and width representing a garden of size height x width. You are also given:

an array tree where tree = [treer, treec] is the position of the tree in the garden, an array squirrel where squirrel = [squirrelr, squirrelc] is the position of the squirrel in the garden, and an array nuts where nuts[i] = [nutir, nutic] is the position of the ith nut in the garden. The squirrel can only take at most one nut at one time and can move in four directions: up, down, left, and right, to the adjacent cell.

Return the minimal distance for the squirrel to collect all the nuts and put them under the tree one by one.

The distance is the number of moves.

URL: https://leetcode.com/problems/squirrel-simulation/

This problem became easier to solve for me once I considered the case where the squirrel starts at the tree. If the squirrel starts at the tree, then the minimum distance is simply the distance from the tree to each nut and back. This case only has one distance possible. If the squirrel starts at a different position, then one of the trips from the tree to the nut gets replaced by the squirrel’s trip to the nut.

Therefore, the idea is I need to to calculate the difference,(trip from tree to nut) - (squirrels trip to nut), for each nut and track the greatest difference. This difference is a savings that then is subtracted from the total distance for the case where the squirrel starts at the tree.

My solution:

class Solution {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        //iterate thru array to maximize fi - xi
        int maxDiff = Integer.MIN_VALUE;
        int dist = 0;
        for (int i = 0; i < nuts.length; i++) {
            int f = Math.abs(nuts[i][0] - tree[0]) + Math.abs(nuts[i][1] - tree[1]);
            int x = Math.abs(nuts[i][0] - squirrel[0]) + Math.abs(nuts[i][1] - squirrel[1]);
            maxDiff = Math.max(maxDiff, f-x);
            dist += 2*f;
        }
        return dist - maxDiff;
    }
}

Explanation:

Line 6 iterates through the nuts array.

Line 7 calculates the one-way distance from the tree to the nut.

Line 8 calculates the distance from the squirrels initial position to the nut.

Line 9 stores the maximum difference so far for (trip from tree to nut) - (squirrels trip to nut).

Line 10 calculates the total distance traveled for the hypothetical case where the squirrel starts at the tree.

Line 12 subtracts the maximum difference as savings from the hypothetical total distance. If the squirrel does indeed start at the tree, then the maximum difference will be 0 which also returns the expected result.