Problem statement

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

Solution

Let $A$ and $B$ be positions of squirrel and tree and $N_1,\dots N_n$ are positions of nuts. Then if we visit first nut number $k$, the distance will be \(\rho(A, N_k) + \rho(N_k, B) + \sum\limits_{i\neq k}2\rho(N_i, B) =\) \(=2\sum\limits_{i}\rho(N_i,B) + \rho(A, N_k) - \rho(N_k, B).\)

So, we need to evaluate $2\sum\limits_i\rho(N_i,B)$ and find $\min\limits_k \rho(A, N_k) - \rho(N_k, B)$.

Complexity

Both steps can be done in O(n). So, time complexity is O(n), space complexity is O(1).

Code

class Solution:
    def minDistance(self, H, W, tree, squirrel, nuts):
        def dist(A, B):
            return abs(A[0] - B[0]) + abs(A[1] - B[1])
        
        part1 = sum(dist(tree, nut) for nut in nuts)
        part2 = min(dist(squirrel, nut) - dist(tree, nut) for nut in nuts)
        return 2*part1 + part2