Squirrel Simulation solution and explanation
4 more videos on this problem
LC Premium 573. Squirrel Simulation | One Pass | Two Pass | O(n) timeAryan Mittal · 12:20 · 734 views
573. Squirrel Simulation - Week 2/5 Leetcode November ChallengeProgramming Live with Larry · 8:30 · 474 views
Leetcode: Squirrel SimulationLester Minnick · 6:00 · 291 views
LeetCode 573: Squirrel SimulationAlitaCode · 26:59 · 7 views
[Leetcode Weekly Nov 2/5] 573. Squirrel Simulation (Python 中文解說)陳逸星 · 10:37 · 1 view
The problem
You are given two integers height and width representing a garden of size height x width. You are also given:
- an array
treewheretree = [treer, treec]is the position of the tree in the garden, - an array
squirrelwheresquirrel = [squirrelr, squirrelc]is the position of the squirrel in the garden, - and an array
nutswherenuts[i] = [nutir, nutic]is the position of theithnut 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.
Example 1:
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.
Example 2:
Input: height = 1, width = 3, tree = [0,1], squirrel = [0,0], nuts = [[0,2]] Output: 3
Constraints:
1 <= height, width <= 100tree.length == 2squirrel.length == 21 <= nuts.length <= 5000nuts[i].length == 20 <= treer, squirrelr, nutir <= height0 <= treec, squirrelc, nutic <= width
Approach overview
Problem Overview: A squirrel starts at a given position in a grid and must collect several nuts, dropping each one at a tree. The squirrel can only carry one nut at a time. Normally every nut trip starts and ends at the tree, except the very first trip which starts from the squirrel’s initial position. The task is to compute the minimum total Manhattan distance needed to collect all nuts.
Approach 1: Brute Force First-Nut Choice (O(n²) time, O(1) space)
Every nut except the first effectively costs 2 * dist(nut, tree) because the squirrel goes from the tree to the nut and back. The first nut is different since the squirrel starts at its initial position. One brute-force strategy is to try each nut as the first nut collected. For each candidate, compute the total cost by summing dist(squirrel, nut_i) + dist(nut_i, tree) for the first nut and 2 * dist(nut_j, tree) for the rest. This requires recomputing distances for every candidate, leading to O(n²) time with constant space.
Approach 2: Greedy Math Optimization (O(n) time, O(1) space)
The key observation: if the squirrel started at the tree, the total cost would simply be the sum of 2 * dist(nut, tree) for every nut. The only difference in the real scenario is the first nut. Instead of traveling tree → nut → tree, the squirrel travels squirrel → nut → tree. The change in cost is dist(squirrel, nut) - dist(nut, tree). Iterate through all nuts and find the nut that minimizes this extra cost (or equivalently maximizes the saving dist(nut, tree) - dist(squirrel, nut)). Compute the base cost for all nuts, then adjust it using the best candidate. Distances are simple Manhattan calculations on coordinates stored in an array. This turns the problem into a single linear scan using straightforward math and a small greedy decision.
Recommended for interviews: The greedy mathematical approach is what interviewers expect. It shows you can reduce repeated work by reasoning about the baseline cost and adjusting only the first move. Mentioning the brute-force idea first demonstrates understanding of the movement rules, while the optimized O(n) solution shows strong problem decomposition and distance analysis.
Solution
Observing the squirrel's movement path, we can see that the squirrel will first move to the position of a nut, then move to the position of the tree. After that, the total movement path of the squirrel is equal to "the sum of the distances from the remaining nuts to the tree" multiplied by 2.
Therefore, we only need to select a nut as the squirrel's first target, such that the sum of its distance to the tree is minimized, to obtain the shortest path.
The time complexity is O(n), where n is the number of nuts. The space complexity is O(1).
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 ansimport static java.lang.Math.*;
class Solution {
public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
int tr = tree[0], tc = tree[1];
int sr = squirrel[0], sc = squirrel[1];
int s = 0;
for (var e : nuts) {
s += abs(e[0] - tr) + abs(e[1] - tc);
}
s <<= 1;
int ans = Integer.MAX_VALUE;
for (var e : nuts) {
int a = abs(e[0] - tr) + abs(e[1] - tc);
int b = abs(e[0] - sr) + abs(e[1] - sc);
ans = min(ans, s - a + b);
}
return ans;
}
}class Solution {
public:
int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {
int tr = tree[0], tc = tree[1];
int sr = squirrel[0], sc = squirrel[1];
int s = 0;
for (const auto& e : nuts) {
s += abs(e[0] - tr) + abs(e[1] - tc);
}
s <<= 1;
int ans = INT_MAX;
for (const auto& e : nuts) {
int a = abs(e[0] - tr) + abs(e[1] - tc);
int b = abs(e[0] - sr) + abs(e[1] - sc);
ans = min(ans, s - a + b);
}
return ans;
}
};function minDistance(
height: number,
width: number,
tree: number[],
squirrel: number[],
nuts: number[][],
): number {
const [tr, tc] = tree;
const [sr, sc] = squirrel;
const s = nuts.reduce((acc, [r, c]) => acc + (Math.abs(tr - r) + Math.abs(tc - c)) * 2, 0);
let ans = Infinity;
for (const [r, c] of nuts) {
const a = Math.abs(tr - r) + Math.abs(tc - c);
const b = Math.abs(sr - r) + Math.abs(sc - c);
ans = Math.min(ans, s - a + b);
}
return ans;
}public class Solution {
public int MinDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
int tr = tree[0], tc = tree[1];
int sr = squirrel[0], sc = squirrel[1];
int s = 0;
foreach (var e in nuts) {
s += Math.Abs(e[0] - tr) + Math.Abs(e[1] - tc);
}
s <<= 1;
int ans = int.MaxValue;
foreach (var e in nuts) {
int a = Math.Abs(e[0] - tr) + Math.Abs(e[1] - tc);
int b = Math.Abs(e[0] - sr) + Math.Abs(e[1] - sc);
ans = Math.Min(ans, s - a + b);
}
return ans;
}
}func minDistance(height int, width int, tree []int, squirrel []int, nuts [][]int) int {
tr, tc := tree[0], tree[1]
sr, sc := squirrel[0], squirrel[1]
s := 0
for _, e := range nuts {
s += abs(e[0]-tr) + abs(e[1]-tc)
}
s <<= 1
ans := math.MaxInt32
for _, e := range nuts {
a := abs(e[0]-tr) + abs(e[1]-tc)
b := abs(e[0]-sr) + abs(e[1]-sc)
ans = min(ans, s-a+b)
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn min_distance(
height: i32,
width: i32,
tree: Vec<i32>,
squirrel: Vec<i32>,
nuts: Vec<Vec<i32>>,
) -> i32 {
let (tr, tc) = (tree[0], tree[1]);
let (sr, sc) = (squirrel[0], squirrel[1]);
let s: i32 = nuts
.iter()
.map(|nut| (nut[0] - tr).abs() + (nut[1] - tc).abs())
.sum::<i32>()
* 2;
let mut ans = i32::MAX;
for nut in &nuts {
let a = (nut[0] - tr).abs() + (nut[1] - tc).abs();
let b = (nut[0] - sr).abs() + (nut[1] - sc).abs();
ans = ans.min(s - a + b);
}
ans
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force First-Nut Simulation | O(n²) | O(1) | Useful for reasoning about the problem or verifying correctness with small inputs |
| Greedy Mathematical Optimization | O(n) | O(1) | Best choice for interviews and production; computes base distance once and adjusts using the optimal first nut |
Frequently asked questions
Is Squirrel Simulation easy or hard?
Squirrel Simulation is rated Medium because the challenge is recognizing the mathematical shortcut. The implementation is simple once you realize that every nut normally costs 2 * dist(nut, tree) and only the first trip changes the total distance.
Squirrel Simulation Python/Java solution
Both Python and Java implementations follow the same logic: compute the base distance 2 * dist(nut, tree) for all nuts, track the maximum saving dist(nut, tree) - dist(squirrel, nut), and add that adjustment to the total. The algorithm runs in O(n) time with constant extra space.
How to solve Squirrel Simulation in O(n)?
First compute the base total distance as the sum of 2 * dist(nut, tree) for all nuts. Then iterate through the nuts and calculate the adjustment value dist(nut, tree) - dist(squirrel, nut). The nut with the maximum saving should be collected first. Add this adjustment to the base total to get the minimum distance.
What is the best approach for Squirrel Simulation?
The optimal approach uses a greedy mathematical observation. First compute the baseline cost assuming the squirrel starts at the tree, which is 2 * Manhattan distance from each nut to the tree. Then adjust the total by choosing the nut that maximizes the saving dist(nut, tree) - dist(squirrel, nut). This reduces the problem to a single O(n) scan.
Is Squirrel Simulation asked at Google/Amazon/Meta?
Squirrel Simulation is a medium-level grid and distance optimization problem commonly seen in interview preparation platforms like LeetCode. Variations of Manhattan distance optimization and greedy selection appear in interviews at large tech companies including Google and Amazon.
What data structure is used in Squirrel Simulation?
The problem primarily uses arrays or lists to store nut coordinates. The main computation relies on Manhattan distance math and a linear scan through the array of nuts, so no advanced data structures are required.
What is the time complexity of Squirrel Simulation?
The optimal solution runs in O(n) time where n is the number of nuts. Each nut is processed once to compute its distance to the tree and to the squirrel. Space complexity is O(1) since only a few running variables are needed.