LeetCode 573: Squirrel Simulation

Problem Restatement

We are given a garden grid with a tree, a squirrel, and several nuts.

The squirrel must collect all nuts and put them under the tree one by one.

The squirrel can carry at most one nut at a time. It can move one cell at a time in four directions: up, down, left, and right.

Return the minimum total distance the squirrel must move.

The problem gives height, width, tree, squirrel, and nuts. There is at least one nut, and the given positions do not overlap. The example height = 5, width = 7, tree = [2,2], squirrel = [4,4], nuts = [[3,0], [2,5]] has output 12.

Input and Output

Example function shape:

def minDistance(
    height: int,
    width: int,
    tree: list[int],
    squirrel: list[int],
    nuts: list[list[int]],
) -> int:
    ...

Examples

Example 1:

height = 5
width = 7
tree = [2, 2]
squirrel = [4, 4]
nuts = [[3, 0], [2, 5]]

Distance from nut [3, 0] to the tree:

abs(3 - 2) + abs(0 - 2) = 3

Distance from nut [2, 5] to the tree:

abs(2 - 2) + abs(5 - 2) = 3

If the squirrel starts at the tree for every nut, the total would be:

2 * 3 + 2 * 3 = 12

But the squirrel does not start at the tree. It starts at [4, 4].

If it picks nut [2, 5] first:

squirrel to nut = abs(4 - 2) + abs(4 - 5) = 3
nut to tree = 3

Then it returns to the tree and collects the other nut with a round trip:

2 * 3 = 6

Total:

3 + 3 + 6 = 12

So the answer is:

12

Example 2:

height = 1
width = 3
tree = [0, 1]
squirrel = [0, 0]
nuts = [[0, 2]]

There is one nut.

The squirrel goes from [0, 0] to [0, 2], then from [0, 2] to the tree [0, 1].

Total:

2 + 1 = 3

So the answer is:

3

First Thought: Try Every Nut Order

A direct solution is to try every order in which the squirrel could collect the nuts.

For each order, simulate the movement and keep the smallest total distance.

This is correct, but it is too slow.

If there are n nuts, there are:

n!

possible orders.

The constraints allow thousands of nuts in common formulations of the problem, so trying all orders is impossible.

Key Insight

Only the first trip is special.

After the squirrel collects the first nut and drops it under the tree, the squirrel is at the tree.

From then on, every remaining nut costs:

tree -> nut -> tree

So every remaining nut contributes:

2 * distance(nut, tree)

The only decision is which nut to collect first.

For the first nut, the cost is:

distance(squirrel, nut) + distance(nut, tree)

Instead of:

2 * distance(nut, tree)

So compared with the baseline, choosing a nut first changes the total by:

distance(squirrel, nut) - distance(nut, tree)

We want this adjustment to be as small as possible.

Equivalently, we want to maximize the saving:

distance(nut, tree) - distance(squirrel, nut)

This is the standard linear solution: compute the total round-trip distance from the tree to every nut, then subtract the best first-trip saving.

Manhattan Distance

Because the squirrel moves only in four directions, the shortest distance between two grid positions is Manhattan distance:

abs(r1 - r2) + abs(c1 - c2)

For example:

[4, 4] to [2, 5]

has distance:

abs(4 - 2) + abs(4 - 5) = 3

Algorithm

1. Define a helper function dist(a, b) for Manhattan distance.
2. Initialize:

   total = 0
   best_saving = -infinity
3. For each nut:
   1. Compute tree_dist = dist(nut, tree).
   2. Compute squirrel_dist = dist(nut, squirrel).
   3. Add 2 * tree_dist to total.
   4. Update:

      best_saving = max(best_saving, tree_dist - squirrel_dist)
4. Return:

   total - best_saving

Correctness

Assume the squirrel chooses some nut x first.

For this first nut, the squirrel moves from its starting position to x, then from x to the tree.

The cost is:

dist(squirrel, x) + dist(x, tree)

After that, the squirrel is at the tree.

For every other nut y, the squirrel must go from the tree to y, then return from y to the tree. The cost is:

2 * dist(y, tree)

So for a fixed first nut x, the total cost is:

sum(2 * dist(nut, tree) for every nut)
- dist(x, tree)
+ dist(squirrel, x)

The first large sum is the same no matter which nut is chosen first.

Therefore, minimizing the total cost is equivalent to minimizing:

dist(squirrel, x) - dist(x, tree)

or equivalently maximizing:

dist(x, tree) - dist(squirrel, x)

The algorithm checks every nut as the possible first nut and chooses the maximum saving. Therefore, it returns the minimum possible total distance.

Complexity

Let n be the number of nuts.

Implementation

class Solution:
    def minDistance(
        self,
        height: int,
        width: int,
        tree: list[int],
        squirrel: list[int],
        nuts: list[list[int]],
    ) -> int:
        def dist(a: list[int], b: list[int]) -> int:
            return abs(a[0] - b[0]) + abs(a[1] - b[1])

        total = 0
        best_saving = float("-inf")

        for nut in nuts:
            tree_dist = dist(nut, tree)
            squirrel_dist = dist(nut, squirrel)

            total += 2 * tree_dist
            best_saving = max(best_saving, tree_dist - squirrel_dist)

        return total - best_saving

Code Explanation

The helper function computes Manhattan distance:

def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

For each nut, we first compute its normal round-trip cost from the tree:

total += 2 * tree_dist

This assumes every trip starts at the tree.

Then we compute the saving if this nut is collected first:

tree_dist - squirrel_dist

If this value is large, choosing this nut first saves more distance.

Finally:

return total - best_saving

subtracts the best first-trip saving from the baseline total.

Testing

def run_tests():
    s = Solution()

    assert s.minDistance(
        5,
        7,
        [2, 2],
        [4, 4],
        [[3, 0], [2, 5]],
    ) == 12

    assert s.minDistance(
        1,
        3,
        [0, 1],
        [0, 0],
        [[0, 2]],
    ) == 3

    assert s.minDistance(
        3,
        3,
        [1, 1],
        [1, 1],
        [[0, 0], [2, 2]],
    ) == 8

    assert s.minDistance(
        4,
        4,
        [0, 0],
        [3, 3],
        [[0, 1], [3, 0]],
    ) == 10

    print("all tests passed")

run_tests()