# 573. Squirrel Simulation

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public: int minDistance(int height, int width, vector& tree, vector& squirrel, vector>& nuts) { int totDist = 0; int maxSave = INT_MIN; for (const vector& nut : nuts) { totDist += dist(nut, tree) * 2; maxSave = max(maxSave, dist(nut, tree) - dist(nut, squirrel)); } return totDist - maxSave; } private: int dist(const vector& a, const vector& b) { return abs(a[0] - b[0]) + abs(a[1] - b[1]); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) { int totDist = 0; int maxSave = Integer.MIN_VALUE; for (int[] nut : nuts) { totDist += dist(nut, tree) * 2; maxSave = Math.max(maxSave, dist(nut, tree) - dist(nut, squirrel)); } return totDist - maxSave; } private int dist(int[] a, int[] b) { return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]); } } 
 1 2 3 4 5 6 7 8 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]) totDist = sum(dist(nut, tree) for nut in nuts) * 2 maxSave = max(dist(nut, tree) - dist(nut, squirrel) for nut in nuts) return totDist - maxSave