Squirrel Simulation — LeetCode 573 Python Solution

The problem

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.

Example

Input

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

Output

12

Explanation

The squirrel should go to the nut at [2, 5] first to achieve a minimal distance.

Python solution

class Solution:
    def minDistance(
        self,
        height: int,
        width: int,
        tree: List[int],
        squirrel: List[int],
        nuts: List[List[int]],
    ) -> int:
        tr, tc = tree
        sr, sc = squirrel
        s = sum(abs(r - tr) + abs(c - tc) for r, c in nuts) * 2
        ans = inf
        for r, c in nuts:
            a = abs(r - tr) + abs(c - tc)
            b = abs(r - sr) + abs(c - sc)
            ans = min(ans, s - a + b)
        return ans

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 573. Squirrel Simulation is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems